【每日算法Day 77】两数/三数之和

LeetCode 1. 两数之和 (opens new window)

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

如果使用双重循环搜索时间复杂度为O(n^2)，可以使用哈希表，扫描每一个数num时检查target-num是否在哈希表中，有则返回，没有则把num和其下标放入集合中。使用O(n)的空间和时间。

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

LeetCode 15. 三数之和 (opens new window)

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

排序数组后，从左向右固定a，再对a后面的部分使用双指针法搜索符合条件的b和c，注意b和c在移动时如果发现和前一个数字相同则继续移动。双指针法搜索两个数时间复杂度为O(n)，则总是时间复杂度为O(n*n)+O(nlogn)=O(n^2)，排序用到的空间复杂度为O(n)。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; ) {
        if (nums[i] > 0) break;
        int j = i + 1, k = nums.length - 1;
        while (j < k) {
            if (nums[j] + nums[k] == -nums[i]) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[i]);
                list.add(nums[j]);
                list.add(nums[k]);
                result.add(list);
                while (j + 1 < k && nums[j + 1] == nums[j])
                    j++;
                j++;
                while (k - 1 > j && nums[k - 1] == nums[k])
                    k--;
                k--;
            }
            if (nums[j] + nums[k] > -nums[i]) {
                while (k - 1 > j && nums[k - 1] == nums[k])
                    k--;
                k--;
            }
            if (nums[j] + nums[k] < -nums[i]){
                while (j + 1 < k && nums[j + 1] == nums[j])
                    j++;
                j++;
            }
        }
        while (i + 1 < nums.length && nums[i + 1] == nums[i])
            i++;
        i++;
    }
    return result;
}