leetcode - [18] 4Sum

2020/06/29

问题描述

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

从整数数组中找出和为0的四个元素,注意结果的唯一性。

举个例子:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

类似题:

[15] 3Sum

解法1

解法与 [15] 3Sum 类似。

注意,第二层循环的判重条件:

if (j > i + 1 && nums[j] == nums[j - 1]) continue;

来看下实现:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        
        List<List<Integer>> ans = new LinkedList<>();
        int len = nums.length;
        if (len < 4) return ans;
        Arrays.sort(nums);
        
        // [0, 0, 0, 0]
        for (int i = 0; i < len - 3; i++){
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int first = nums[i];
            for (int j = i + 1; j < len - 2; j++){
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int second = nums[j];
                int rest = target - first - second;
                int lo = j + 1;
                int hi = len - 1;
                while (lo < hi){
                    int sum = nums[lo] + nums[hi];
                    if (sum == rest){
                        ans.add(Arrays.asList(first, second, nums[lo], nums[hi]));
                        while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                        while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                        lo++;
                        hi--;
                    } else if (sum < rest){
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
        }
        return ans;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory