3Sum

问题描述

Given an array S of n integers, are there elements a , b , c in S such that a + b + c = 0?

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
　　(-1, 0, 1)
　　(-1, -1, 2)

这题的意思是，在给出的整数数组中，找出三个元素的和为0的集合，集合中的元素是升序排列，同时集合中不能包含重复的解。

解法

前面我们解过一个Two Sum的问题，这里虽说是三个数了，但是乍一看会让人去思考：是不是可以用和Two Sum问题相似的解法？我想可以尝试一下，大概思路即：在数组中取一个元素，求它的反，然后在剩下的元素中找到两个数，它们的和正好和前面求得的反相等。值得注意的地方：

• 这一题最终不是求元素的索引。
• 这一题不用考虑是否有多个相同的元素，因为最终的集合不包含重复的解。

class Solution
{
  public List<List<Integer>> threeSum(int[] nums)
  {
    List<List<Integer>> result = new List<List<Integer>>();
    if(nums.length < 3) return result;
    Arrays.sort(nums);
    for(int i = 0;i < nums.length;i++)
    {
      if(nums[i]>0)
      break;
      if(i > 0 && nums[i] == nums[i-1])
      continue;
      int begin = i+1,end = nums.length - 1;
      while(begin < end)
      {
        int sum = nums[i] + nums[begin] + nums[end];
        if(sum == 0)
        {
          List<Integer> list = new ArrayList<Integer>();
          list.add(nums[i]);
          list.add(nums[begin]);
          list.add(nums[end]);
          result.add(list);
          begin++;
          end--;
          while(begin < end && nums[begin] == nums[begin-1])
          begin++;
          while(begin < end && nums[end] == nums[end+1])
          end--;
        }
        else if(sum > 0)
        end--;
        else
        begin++;
        }
      }
    }
  return result;
  }
}