leetcode100hot

题库为leetcode的热门100题

https://leetcode.cn/studyplan/top-100-liked/

1、哈希

1、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 
提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

不算特别难，可以直接暴力枚举（当然我也就只会这个了）

leetcode official wp:
1、枚举
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];
    }
}

https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/

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

更快的方法是使用哈希表实现快速搜索，因为其中的一个数是必然存在另一个数跟其匹配的，如果存在正确答案的话。对所有元素进行遍历，寻找每一个元素在哈希表中是否存在与其匹配的元素，如果不存在就将该元素写入哈希表，存在则直接返回正确答案了。（本题只存在唯一正确答案，因此直接结束程序，如果有多个答案也可以全部执行）

小结：如果需要进行快速匹配或者快速搜索时可以使用哈希表

吐槽：由于刚开始是用c写的，那个returnsize真的抽象，完全不知道是用来干嘛的。而且用c写的话还得自己维护一个哈希表，想了想非常麻烦，所以后面都用jvav写了。

2、字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]

解题思路：可以对每个字母分为字符数组进行排序，将排序后的字符串作为map的key，原字符串作为map的value，就可以得到正确的结果。

wp:
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> res = new HashMap<>();
        for(String str:strs){
            char[] strCharArray = str.toCharArray();
            Arrays.sort(strCharArray);
            String sortString = new String(strCharArray);
            if(!res.containsKey(sortString)){
                res.put(sortString,new ArrayList<>());
            }
            res.get(sortString).add(str);
        }
        return new ArrayList<>(res.values());
        
    }
}

leetcode official wp:
1、哈希表
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}
相比于上一段代码，只是使用getOrDefault对map进行了初始化，即存在该键的话读取其值，不存在则生成新的map元素。

2、对字母出现的次数进行计数
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

很好理解，而且思路也很简单

3、最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：

输入：nums = [1,0,1,2]
输出：3

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

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

        int longest = 0;
        for (int num : numset) {
            if (!numset.contains(num - 1)) {
                int initial = num;
                int next = num + 1;
                int count = 1;
                while (numset.contains(next)) {
                    next++;
                    count++;
                }
                if (count > longest) {
                    longest = count;
                }
            }
        }
        return longest;
    }
}
将所有的数存入集合中，可以对数据进行去重，还方便对数字进行搜索。
hashset是由java的hashmap类实现的，哈希表由哈希函数生成，基本操作都是O(1)级别。
存入集合后对数据进行查找，判断该数据是否为序列的起始数据，通过集合中是否包含上一个连续数据即可得知，在寻找到起始数据之后，就可以计算出序列的长度，再比较得到最长的长度。

对于算法的时间复杂度，其实嵌套了两个循环，按照一般的想法这个算法可能是n^2的级别，但是由于在本题中，所有数据只会被操作两次或者三次，所以算法的时间复杂度是在O(n)级别。

官方题解也是这个思路，但是如果你点开用时最短的题解，会发现人家直接用快排了（难绷

2、双指针

1、移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

自己写的解法，非常慢且开销大

wp:
class Solution {
    public void moveZeroes(int[] nums) {
        for(int i=0;i<nums.length;i++)
        {
            int j=i+1;
            if(nums[i]==0 && j<nums.length){
                while(nums[j]==0){
                    j++;
                    if(j>=nums.length)
                    {
                        break;
                    }
                }
                if(j>=nums.length)
                {
                    break;
                }
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
    }
}

将序列为分两部分，左指针指向非零序列，右指针指向未排序的序列的首个非零项。
official wp:
class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length,left=0,right=0;
        while(right<n)
        {
            if(nums[right]!=0){
                swap(nums,left,right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

fastest wp:
class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0, j = 0;
        int len = nums.length;
        while(i < len && j < len) {
            if(nums[i] != 0) {
                nums[j++] = nums[i++];
            }else {
                i++;
            }
        }
        for(i = j; i < len; i++) {
            nums[i] = 0;
        }
    }
}

2、盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：

输入：height = [1,1]
输出：1

wp
class Solution {
    public int maxArea(int[] height) {
        int left = 0,right = height.length-1;
        int max = 0;
        while(left<right){
            int temp = Math.min(height[left],height[right])*(right-left);
            if(height[left] < height[right]){
                left++;
            }
            else{
                right--;
            }
            max = Math.max(max,temp);
        }
        return max;
    }
}

双指针算法的正确性来源于每次移动的都是较短高度的指针，根据计算容积的公式可以得到，被移动的指针对应的高度可能会减少或者增加，但是计算时用到的高度只会不高于不移动的指针对应的高度，而此时宽度又在减少，因此总的容积是在减少的，也就是说，初始状态就是最佳状态，除非移动之后能找到更高的高度，才可能出现最大值的变换。因此每次移动较短高度的指针即可排除掉错误的情况。

3、三数之和

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-1;i++){
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }

            int left = i + 1;
            int right = nums.length-1;
            while(left<right){
                int sum = nums[left] + nums[i] + nums[right];
                if(sum == 0){
                    res.add(Arrays.asList(nums[left],nums[i],nums[right]));
                    while(left<right && nums[left] == nums[left+1])
                    {
                        left++;
                    }
                    while(left<right && nums[right] == nums[right-1])
                    {
                        right--;
                    }
                    left++;
                    right--;
                }
                if(sum > 0){
                    right--;
                }
                if(sum <0){
                    left++;
                }
            }
            
        }
        return res;
    }
}

得先排序，个人感觉双指针还是界定范围的功能比较大，如果没有办法让结果呈现固定的趋势变化就很难使用双指针来实现。

4、接雨水

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int left = 0,right = height.length-1;
        int leftMax = height[left];
        int rightMax = height[right];
        while(left<right){
            if(leftMax<rightMax){
                left++;
                leftMax = Math.max(leftMax,height[left]);
                res += leftMax - height[left];
            }
            else{
                right--;
                rightMax = Math.max(rightMax,height[right]);
                res += rightMax - height[right];
            }
        }
        return res;
    }
}

解法很简洁，虽然想不到，正确性需要证明。

3、滑动窗口

1、无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> charset = new HashSet<>();
        int res = 0,left = 0,right = 0;Q
        for(right=0;right<s.length();right++){
            while(charset.contains(s.charAt(right))){
                charset.remove(s.charAt(left));
                left++;
            }
            charset.add(s.charAt(right));
            res = Math.max(res,charset.size());
        }
        return res;
    }
}

有点像双指针，同样是界定了一个范围，再进行操作。

2、找到字符串中所有字母异位词

wp:
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] pchar = p.toCharArray();
        Arrays.sort(pchar);
        String pnew = new String(pchar);
        int windowlength = p.length();
        char[] schar = p.toCharArray();
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0;i<=s.length()-p.length();i++){
            String temp = s.substring(i,i+p.length());
            char[] tempchar = temp.toCharArray();
            Arrays.sort(tempchar);
            String tempnew = new String(tempchar);
            if(tempnew.equals(pnew)){
                res.add(i);
            }

        }
        return res;
    }
}

过是过了，就是很慢。

官方题解给出的优化算法是统计相同字符的个数，以及统计相同字符的差值，比起比较整个字符串是否相同要快得多。

4、子串

1、和为k的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res=0;
        for(int i=0;i<nums.length;i++){
            int left = i;
            int right=left;
            int sum = nums[left];
            if(sum == k)
            {
                res ++;
            }
            while(right<nums.length){
                right++;
                if(right>=nums.length){
                    break;
                }
                sum+=nums[right];
                if(sum == k)
                {
                    res ++;
                }
            }
        }
        return res;
    }
}

也是暴力出来了，虽然很慢。

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

官方题解：利用前缀和减少计算量，使用hashmap计算符合条件的值的次数。