目录

49、字母易位词分组

128、最长连续序列

283、移动零

11、盛最多水的容器

15、三数之和

---

49、字母易位词分组

题目：

思路一：排序
将数组中的字母按照a~z的顺序排序，排序后的字母作为HashMap的一个key，value为一个List，List里存与key相同的值。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //创建一个hashmap key存排序后Strs中的值，values为一个List
        //里面存放排序前Strs的值，最后返回的也是这个list
        //遍历字符串数组
        //将字符串转化为字符数组
        //将字符数组进行排序
        //若map键中不存在转化后的字符串，则值生成一个新List集合
        //若存在，则返回key对应值的List集合
        Map<String,List<String>> map = new HashMap<>();
        List<String> l ;
        for(String s : strs){
            //char[] array = str.toCharArray();
            char [] array= s.toCharArray();
            Arrays.sort(array);
            String newstr = new String(array);
            if(map.containsKey(newstr)){
                l = map.get(newstr);
            }
            else{
                l = new ArrayList<>();
            }
            l.add(s);
            map.put(newstr,l);
        }

        return new ArrayList<List<String>>(map.values());


    }
}

toCharArray()；将字符串转化为字符数组
Arrays.sort(array);对数组进行排序
 return new ArrayList<List<String>>(map.values());

128、最长连续序列

题目：

思路：将数组放到哈希表中去重；在这个哈希表中，判断当前数值-1是否存在（也就是判断是否为起点），不存在则证明是起点，进入一个循环，不断判断当前数值+1是否存在，存在则序列数+1，不存在则结束。
 

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet();
        int sumcount = 0;
        for(int num : nums){
            set.add(num);
        }

        for(int num : set){
            if(!set.contains(num-1)){
                int count = 1;
                while(set.contains(num+1)){
                    count++;
                    num++;
                }

                sumcount = Math.max(count,sumcount);
            }
        }

        return sumcount;

    }
}

283、移动零

题目：

双指针法
思路：右指针r依次指向每个非0元素，左指针l指向当前已经处理好的序列的尾部

class Solution {
    public void moveZeroes(int[] nums) {
        for(int r = 0 , l = 0 ; r < nums.length ; r++){
            
            if(nums[r] != 0){
                
                int temp = nums[r];
                nums[r] = nums[l];
                nums[l] = temp;
                l++;
            }
        }
        
    }
}

11、盛最多水的容器

题目：

双指针法
思路：
首先思考计算最大容量的公式： s = （右 - 左）*高 ；高是左右水柱相对更矮的那一个
接下来便是指针移动的问题：我们应当移动相对矮的那个指针，因为移动相对矮的那个指针，高才可能变高，在移动过程中（右-左）是一定变小的；故移动相对矮的那个指针。

class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length -1;
        int maxs = 0;
        int s = 0;
        while(r>l){
            s = (r - l)*Math.min(height[r],height[l]);
            maxs = Math.max(s,maxs);
            if( height[l]> height[r]){
                r--;
            }else{
                l++;
            }
        }

        return maxs;
    }
}

15、三数之和

题目

最开始想着用暴力，但是暴力枚举法有点难以去重。要达到去重，思路一般是哈希或者排序，这里用排序好点。

思路一：排序+双指针
整体思路：
先将数组进行排序，遍历排序后的数组，我们要找当前元素i之后两个数字加上当前元素为0；这不就想当于一个目标值会变的两数之和嘛；
左指针l指向i + 1，右指针r执向nums.length-1；如果三数之和大于0，r--,小于0则l++;

难点：去重
一、对于数组中相同的元素i没必要重复求三数之和。if(i > 0 && nums[i] == nums[i - 1]){ continue;//去重}
比如：【0，0,0,1,1,1,1】只需对第一个0和第一个1进行一次三数之和求和即可，刚好对应（i > 0 && nums[i] == nums[i - 1]）这个条件
二、如果遇到一大串相同的l(比如【-1,0,0,0,1】），l指向0时，如果不去重，则会出现三个一样的值。while( l < r && nums[l] == nums[l - 1]){l++;}
具体一点：当i指向了-1，l指向了0，r指向了1，这满足了三数之和。但是面临着一大串0，会重复取值，所以需要去重while( l < r && nums[l] == nums[l - 1]){l++;}

优化：if(nums[i] > 0)break;//优化一：如果当前数字大于0，那三数之和一定大于0（从击败45到击败82）

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;//去重
            }
            if(nums[i] > 0)break;//优化一：如果当前数字大于0，那三数之和一定大于0（从击败45到击败82）
            int l = i + 1;//左指针
            int r = nums.length - 1;//右指针
            while( l < r){
                if(nums[l] + nums[r] + nums [i] == 0){
                    List<Integer> result0 = new ArrayList<>();
                    result0.add(nums[i]);
                    result0.add(nums[l]);
                    result0.add(nums[r]);
                    
                    result.add(result0);
                    l++;
                    while( l < r && nums[l] == nums[l - 1]){l++;}
                    
                }else if(nums[l] + nums[r] + nums [i] > 0){
                    r--;
                }else{
                    l++;
                }
            }
        }

        return result;

    }
}