3sum问题

leetcode

java

1.问题描述

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

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

]

题目翻译：

一个给定的数组中，是否存在a,b,c满足a+b+c=0？找出这个数组中所有满足条件的三元组，同时答案中不能包含重复的情况。

2.解题思路

看到3sum问题，首先想到的是2sum问题，在解决2sum问题的时候，是使用HashMap()来寻找差值，并解决重复问题。而3sum问题内部是一个变化了的2sum问题，因为当确定了a的时候，就需要在剩下的数值中寻找b+c=-a，又变成一个寻找等于任意可能数值2sum问题了。

这里在解决内层2sum问题的时候，使用的类似解决water container的方法，使用两个指针指向数组的头和尾，通过判断两者想加的sum来对位置进行调整，为了避免重复，相同的数值略过处理。

3.代码实现

          class Solution { 
    public List<List<Integer>> threeSum(int[] nums) { 
          int len = nums.length; 
  List<List<Integer>> res = new ArrayList<List<Integer>>(); 
    //注意List<>是一个抽象类，它的实例化要用子类来完成。    
  if(len<=2) 
   return res; 
  Arrays.sort(nums);  //实现排序的类都实现了comparable接口 
  int target = 0; 
  for(int i=0;i<=len-2;i++) { 
       int tmp = target - nums[i]; 
    if(i>0&&nums[i]==nums[i-1])//处理重复问题，同时也解决了i=0的边界问题 
     continue; 
    if(nums[i]>0)//当数值大于0的时候，停止寻找，因为是从负数开始查找的 
     break; 
    int l = i+1; 
    int r = len-1; 
    while(l<r){ 
     int sum= nums[l]+nums[r]; 
     if(tmp==sum) { 
      res.add(Arrays.asList(nums[i], nums[l], nums[r])); 
      while(l<r&&nums[l]==nums[l+1])//处理重复数值 
       l++; 
      while(l<r&&nums[r]==nums[r-1])//处理重复数值问 
       r--; 
      l++; 
      r--; 
     } 
     else if(tmp<sum) { 
      r--; 
     } 
     else { 
      l++; 
        } 
   } 
  } 
  return res; 
    } 
} 

转载于:https://www.cnblogs.com/chailinbo/p/7559920.html

你可能感兴趣的文章