leetcode - [15] 3Sum

2020/06/29

问题描述

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

The solution set must not contain duplicate triplets.

给你一个整数数组,找出和为0三个元素

最终的结果不能包含重复的答案。

举个例子:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

Update at 2020_0720

多谢Y总

思路和之前一样,只是可以简化一下实现:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        Arrays.sort(nums);
        List<List<Integer>> ans = new LinkedList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++){
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int l = i + 1, r = n - 1;
            while (l < r){
                int s = nums[i] + nums[l] + nums[r];
                if (s == 0) {
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l++] == nums[l]);
                    while (l < r && nums[r--] == nums[r]);
                } 
                else if (s > 0) r--;
                else l++;
            }
        }
        return ans;
    }
}

解法1

Thanks

米开:LeetCode 15. 3Sum

@shpolsky

@yavinci

先来看下示意图:

首先,明确一下此题使用双指针思想,并将大问题拆分为小问题进行解决。

比如,我们最终想要求的是a + b + c = 0

我们可以假设a是第一个元素,也就是a = -4

那么我们只要在剩余的元素中,找到两个和等于-a的元素即可。

有了大致思路后,我们来考虑一下细节:

第一,原始数组必须排序,防止重复计算。

Arrays.sort(nums);

第二,外层的循环遍历,也就是上面确定a的过程中,一定要与保证唯一性。

目的还是为了避免重复计算结果。

if (i > 0 && cur == nums[i - 1]) continue;

第三,一旦通过内层循环找到其中一个结果后,需要继续向内遍历,去除掉重复的值。

while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++;
hi--;

来看下完整实现:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        int len = nums.length;
        List<List<Integer>> ans = new LinkedList<>();
        if (len < 3) return ans;
        Arrays.sort(nums);
        
        for (int i = 0; i < len - 2; i++){
            int cur = nums[i];
            // Avoid unnecessary computation.
            if (cur > 0) break;
            // Skip same result.
            if (i > 0 && cur == nums[i - 1]) continue;
            
            int lo = i + 1;
            int hi = len - 1;
            while (lo < hi){
                int l = nums[lo];
                int r = nums[hi];
                if (l + r == -cur){
                    ans.add(Arrays.asList(cur, l, r));
                    // Avoid same child result
                    while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                    lo++;
                    hi--;
                } else if (l + r < -cur){
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        return ans;
    }
}

Enjoy it !


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

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

Post Directory