Leetcode刷题——哈希表&nSum专题

参考刷题指南

GitHub-CyC2018/Leetcode题解之哈希表

1. 两数之和

暴力遍历法：

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

哈希表法，令元素值作为key映射到相应的作为value的索引，当元素值这个key存在且不是num[i]本身即满足target：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> record = new HashMap<>();

        for (int i = 0; i < nums.length; i++) record.put(nums[i], i);

        for (int j = 0; j < nums.length; j++){
            if (record.containsKey(target - nums[j]) && record.get(target - nums[j]) != j)
                return new int[] {record.get(target - nums[j]), j};
        }

        return new int[] {};
    }
}

知识点

数组转ArrayList的两种方法

int[] nums = {2,1,4,13,4};

Integer[] numInt = Arrays.stream(nums).boxed().toArray(Integer[]::new);
ArrayList<Integer> arrayNums1 = new ArrayList<Integer>(Arrays.asList(numInt));

List<Integer> numList = Arrays.stream(nums).boxed().collect(Collectors.toList());
ArrayList<Integer> arrayNums2 = new ArrayList<Integer>(numList);

167. 两数之和 II - 输入有序数组

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right){
            int sum = numbers[left] + numbers[right];
            if (sum == target) return new int[] {left+1, right+1};
            else if (sum > target) right--;
            else left++;
        }
        return new int[]{};
    }
}

170. 两数之和 III - 数据结构设计

参考labuladong教程：twoSum问题的核心思想

频繁使用find()：

进行 find 的时候有两种情况，举个例子：

情况一：add 了 [3,3,2,5] 之后，执行 find(6)，由于 3 出现了两次，3 + 3 = 6，所以返回 true。

情况二：add 了 [3,3,2,5] 之后，执行 find(7)，那么 key 为 2，other 为 5 时算法可以返回 true。

除了上述两种情况外，find 只能返回 false 了。

class TwoSum {
    Map<Integer, Integer> freq = new HashMap<>();

    /** Initialize your data structure here. */
    public TwoSum() {
        this.freq = new HashMap<>();

    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        freq.put(number, freq.getOrDefault(number, 0) + 1);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (int i: freq.keySet()){
            int other = value - i;
            if (other != i && freq.containsKey(other)) return true;
            else if (other == i && freq.get(other) > 1) return true;
        }
        return false;
    }
}

频繁使用add()（然后超出力扣的时间限制了）：

sum 中储存了所有加入数字可能组成的和，每次 find 只要花费 O(1) 的时间在集合中判断一下是否存在就行了，显然非常适合频繁使用 find 的场景，但不适合频繁使用add的场景。

class TwoSum {
    Set<Integer> sum = new HashSet<>();
    List<Integer> nums = new LinkedList<>();

    /** Initialize your data structure here. */
    public TwoSum() {
        this.sum = new HashSet<>();
        this.nums = new LinkedList<>();

    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        for (int i: nums){
            sum.add(number+i);
        }
        nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        return sum.contains(value);
    }
}

15. 三数之和

参考labuladong教程：一个函数秒杀 nSum 问题

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        return threeSumTarget(nums, 0);
    }

    List<List<Integer>> threeSumTarget(int[] nums, int target){
        List<List<Integer>> res = new ArrayList<>();

        for (int start = 0; start < nums.length - 1; start++){
            int num = nums[start];

            List<List<Integer>> twoRes = twoSum(nums, start + 1, target - num);
            for (List list : twoRes){
                list.add(num);
                res.add(list);
            }
            while (start < nums.length - 1 && nums[start+1] == num) start++; // 如果nums[start+1] == num放前面会报数组越界的错
        }

        return res;
    }

    List<List<Integer>> twoSum(int[] nums, int start, int target){
        int left = start, right = nums.length - 1;

        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 2) return res;

        while (left < right){
            int sum = nums[left] + nums[right];
            int left_init = nums[left], right_init = nums[right];

            if (sum == target){
                List<Integer> a = new ArrayList<>();
                a.add(nums[left]);
                a.add(nums[right]);
                res.add(a);
                while (left < right && nums[left] == left_init) left++;
                while (left < right && nums[right] == right_init) right--;
            }
            else if (sum > target){
                while (left < right && nums[right] == right_init) right--;
            }
            else {
                while (left < right && nums[left] == left_init) left++;
            }
        }
        return res;
    }
}

18. 四数之和

在三数之和的框架上再写一层：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        
        List<List<Integer>> res = new ArrayList<>();

        for (int start = 0; start < nums.length - 1; start++){
            int num = nums[start];

            List<List<Integer>> threeRes = threeSumTarget(nums, start + 1, target - num);
            for (List list : threeRes){
                list.add(num);
                res.add(list);
            }
            while (start < nums.length - 1 && nums[start+1] == num) start++;
        }

        return res;
    }

    List<List<Integer>> threeSumTarget(int[] nums, int s, int target){
        List<List<Integer>> res = new ArrayList<>();

        for (int start = s; start < nums.length - 1; start++){
            int num = nums[start];

            List<List<Integer>> twoRes = twoSum(nums, start + 1, target - num);
            for (List list : twoRes){
                list.add(num);
                res.add(list);
            }
            while (start < nums.length - 1 && nums[start+1] == num) start++; 
        }

        return res;
    }

    List<List<Integer>> twoSum(int[] nums, int start, int target){
        int left = start, right = nums.length - 1;

        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 2) return res;

        while (left < right){
            int sum = nums[left] + nums[right];
            int left_init = nums[left], right_init = nums[right];

            if (sum == target){
                List<Integer> a = new ArrayList<>();
                a.add(nums[left]);
                a.add(nums[right]);
                res.add(a);
                while (left < right && nums[left] == left_init) left++;
                while (left < right && nums[right] == right_init) right--;
            }
            else if (sum > target){
                while (left < right && nums[right] == right_init) right--;
            }
            else {
                while (left < right && nums[left] == left_init) left++;
            }
        }
        return res;
    }
}

基于nSum写的递归框架：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);

        return nSumTarget(nums, 4, 0, target);
    }

    List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target){
        int sz = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (n < 2 || sz < n) return res;

        if (n == 2){ //2Sum base case
            int left = start, right = sz - 1;
            
            while (left < right){
                int sum = nums[left] + nums[right];
                int left_init = nums[left], right_init = nums[right];

                if (sum == target){
                    List<Integer> a = new ArrayList<>();
                    a.add(left_init);
                    a.add(right_init);
                    res.add(a);
                    
                    while (left < right && nums[left] == left_init) left++;
                    while (left < right && nums[right] == right_init) right--;
                }
                else if (sum < target){
                    while (left < right && nums[left] == left_init) left++;
                }
                else while (left < right && nums[right] == right_init) right--;
            }
        }
        else{ //递归计算(n-1)Sum结果
            for (int i = start; i < sz; i++){
                int num = nums[i];

                List<List<Integer>> res_temp = nSumTarget(nums, n - 1, i + 1, target - num);

                for (List list : res_temp){
                    list.add(num); //(n-1)Sum加上num[i]就是nSum
                    res.add(list);
                }

                while (i < sz - 1 && num == nums[i + 1]) i++;
            }
        }
        return res;
    }
}

217. 存在重复元素

哈希表（用containsKey()方法）：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> value = new HashMap<>();
        
        for (int i: nums){
            if (value.containsKey(i)) return true;
            else value.put(i,1);
        }

        return false;
    }
}

哈希表（用getOrDefault()方法）：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> value = new HashMap<>();
        
        for (int i: nums){
            value.put(i,value.getOrDefault(i, 0) + 1);
            if (value.get(i) > 1) return true;
        }

        return false;
    }
}

哈希集合（遍历后用集合长度与数组长度比对的方法）：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> value = new HashSet<>();
        for (int i: nums){
            value.add(i);
        }

        return value.size() < nums.length;
    }
}

哈希集合（用contains()方法）：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> value = new HashSet<>();
        for (int i: nums){
            if (value.contains(i)) return true;
            value.add(i);
        }
        return false;
    }
}

594. 最长和谐子序列

class Solution {
    public int findLHS(int[] nums) {
        HashMap<Integer, Integer> value = new HashMap<>();

        for (int i : nums){
            value.put(i, value.getOrDefault(i, 0) + 1);
        }

        int max = 0;
        for (int key : value.keySet()){
            int max_temp = Math.max(value.getOrDefault(key+1, 0), value.getOrDefault(key-1, 0)) + value.get(key); //可以简化为max_temp = value.getOrDefault(key+1, 0) + value.get(key); 因为key-1如果有的话在之前肯定会遍历到
            if (max_temp == value.get(key)) continue;
            max = Math.max(max_temp, max);
        }

        return max;
    }
}

128. 最长连续序列

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;

        HashMap<Integer, Integer> values = new HashMap<>();

        for (int i : nums){
            values.put(i, values.getOrDefault(i, 0) + 1);
        }

        List<Integer> sortedValues = values.keySet().stream().sorted().collect(Collectors.toList());

        int max = 0, pre = sortedValues.get(0), count = 1;
        for (int num: sortedValues){
            if (pre + 1 == num){
                count++;
            }
            else{
                max = Math.max(max, count);
                count = 1;
            }
            pre = num;
        }
        max = Math.max(max, count);

        return max;
    }
}