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]
]

解法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