LeetCodeHot100

1.两数之和

解题思路：

1.暴力解法 两个for循环解决问题 时间复杂度为 O(n2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

2.哈希表

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

2.字母异位词分组

解题思路：字母相同，但排列不同的字符串，排序后都一定是相同的。因为每种字母的个数都是相同的，那么排序后的字符串就一定是相同的。

import java.util.*;

public class groupAnagrams {
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> list= groupAnagrams(strs);
        list.forEach(System.out::println);
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        //用map，key存储排序的后的字符串，value就是对应的字符串集合
        Map<String, List<String>> map = new HashMap<>();
        //遍历strs
        for (String str : strs) {
            //讲字符串转为char数组
            char[] chars = str.toCharArray();
            //对字符串进行排序
            Arrays.sort(chars);
            //构建排序后的字符串
            String key = new String(chars);
            //如果map中存在key对应的list，返回该list集合，如果不存在，返回一个新的list集合
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            //将key和value存入map
            map.put(key, list);
        }
        //讲map转为List进行返回
        return new ArrayList<List<String>>(map.values());
    }
}

3.最长连续序列

解题思路：把输入放入map中，然后遍历判断。难点其实是要求时间复杂度为0.这里遍历的时候就需要做判断，只有当一个数是连续序列的第一个数是才进入内存循环

package CodeThink;

import java.util.HashSet;
import java.util.Set;

public class longestConsecutive {
    public static void main(String[] args) {
        int[] nums = {100,4,200,1,3,2};
        int res = longestConsecutive(nums);
        System.out.println(res);
    }

    public static int longestConsecutive(int[] nums) {
        Set<Integer> sets = new HashSet<>();
        for (int num : nums) {
            sets.add(num);
        }
        int max = 0;
        for (int set : sets) {
            if(!sets.contains(set-1)){
                int temp = 0;
                while(sets.contains(set)) {
                   temp++;
                   set++;
                }
                max = Math.max(max, temp);
            }
        }
        return max;
    }
}

4. 移动零

解题思路：

1.双指针移动,右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

class Solution {
    public void moveZeroes(int[] nums) {
        int n=nums.length;
        int left=0,right=0;
        while(right<n){
            if(nums[right]!=0){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
    }
}

2.还可以将非零元素移动到最前面，记录非零元素的最后一个位置，后面的全部置为0

class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[index] = nums[i];
                index++;
            }
        }
        for(int j=index;j<nums.length;j++){
            nums[j] = 0;
        }
    }
}

5.盛最多水的容器

解题思路：

6.三数之和

解题思路：第一反应考虑用哈希表来做，但是很麻烦，需要处理很多去重的问题，用双指针完成，通过排序可以很方便的跳过重复元素

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        //对数组进行排序
        Arrays.sort(nums);
        //对数组进行遍历
        for (int i = 0; i < nums.length; i++) {
            // 如果最小的数大于0，后续的和一定大于0，直接返回结果
            if(nums[i] > 0){
                break;
            }
             // 跳过重复的元素
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }else {
                    // 找到一个满足条件的三元组
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 跳过重复的元素
                    while (left < right && nums[left] == nums[left + 1]) {
                         left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                         right--;
                    }
                    //移动指针，找到其他可能的元素
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}