Leetcode 15. 三数之和-白红宇

Leetcode 15. 三数之和

阅读量：3903 次

发布时间：2019-05-23

本文共 1487 字，大约阅读时间需要 4 分钟。

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[  [-1, 0, 1],  [-1, -1, 2]]

一开始想到的是两个for循环加上二分查找，发现写出来跑的贼慢。。。

但是终归是自己写的。。。还是要贴一下的。。。。

写的贼麻烦，又臭又长。。。

class Solution {public:    vector
   
    
     > threeSum(vector
     
      & nums) {        vector
      
       
        > ve;        if(nums.size()<3)            return ve;        sort (nums.begin(),nums.end(),less
        
         ()); int Size=nums.size(); int temp1=0x3f3f3f3f,temp2=temp1; for (int i=0;i
         
          =Size-2) break; temp1=nums[i]; for (int j=i+1;j
          
           =Size-1) break; temp2=nums[j]; if(j

& nums,int left,int right) { while (left<=right) { int mid=(left+right)>>1; if(nums[mid]==x) return mid; else if(nums[mid]>x) right=mid-1; else left=mid+1; } return -1; }};

看标准程序的代码。。原来还有更简单的办法。。。标准程序是遍历一遍序列，先找出第一个元素a，然后将b和c分别设为当前遍历的位置+1和序列最后一个元素。。然后与0比较，如果小了则b往前移，如果大了，c往后移。。。直到找到为0的点。。。

一定要注意有重复元素的情况。。。

代码如下：

class Solution {public:    vector
   
    
     > threeSum(vector
     
      & nums) {        vector
      
       
        > ve;        if(nums.size()<3)            return ve;        sort (nums.begin(),nums.end(),less
        
         ()); int Size=nums.size(); for (int i=0;i
         
          0&&nums[i]!=nums[i-1]) { int l=i+1,r=Size-1; while(l
          
           0) r--; else l++; } } } return ve; }};

转载地址：http://btaen.baihongyu.com/

你可能感兴趣的文章