设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

LeetCode OJ 之 3Sum (三个数的和)

2014-11-21 22:15:00.0 Leetcode leetcode  
导读:题目: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.给定含有n个整数的数列,求数列中的三个数a,b,c使得a + b + c = 0,找...。。。

题目:

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

给定含有n个整数的数列,求数列中的三个数a,b,c使得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)

思路:

先对数组排序,然后第一个数先固定,后两个数一个在最前,一个在最后,进行遍历。然后第一个数后移,再进行遍历。

代码:

class Solution {public:    vector > threeSum(vector &num)     {        int digit=0;//三个数的和     vector> result;     int len = num.size();     if (len < 3)       return result;     sort(num.begin(), num.end());     for(int i = 0 ; i < len ; i++)     {         //由于题目要求不能有重复的,因此如果当前的数和上次的相同,则忽略            if(i > 0 && num[i]==num[i-1])                      continue;        int j = i + 1;      int k = len - 1;      while(j < k)      {          //同上       if(j < i + 1 && num[j] == num[j-1])       {        j++;        continue;       }       if(k < len -1 && num[k] == num[k+1])       {        k--;        continue;       }       //如果当前三个数和较小,则j向后移动,使得总数增大       if(num[j] + num[k] + num[i] < digit)       {        j++;       }       else       {        if(num[j] + num[k] + num[i] > digit)        {         k--;        }        else        {         vector cur;//在这里面定义可以把上次循环的cur覆盖掉         cur.push_back(num[i]);         cur.push_back(num[j]);         cur.push_back(num[k]);         result.push_back(cur);         j++;         k--;        }           }      }     }     return result;    }};



(编辑: )

网友评论
相关文章