做几个leetcode数组题二 - c++编程基础

我那个思路也是应该可行的，只是注意对特殊边界的处理，这里是第一个，所以改成这个版本后就AC了哈哈（一开始没AC是马虎了，r2写r1）。（注意这种排除重复的满足条件的三个数的前提是排好序了）

 vector
    
     > threeSum(vector
     
       &num) {

        vector
     
      ::iterator r1;

        vector
     
      ::iterator r2;

		const int target = 0;

		vector
    
     > result;

		if (num.size() < 3) return result;

		sort(num.begin(),num.end());

        for (r1 = num.begin(); r1 < prev(num.end(), 2); ++r1)

    	    if (r1 > num.begin()&&(*r1 == *prev(r1))) continue;
  //这里注意顺序，先保证不是第一个，再进行prev,原本用了两个连if，觉得太不规范了， 但是Run Time 却从288到了328ms,难道 if (r1 > num.begin()) if((*r1 == *prev(r1))) continue;比 &&快？

    		int a = *r1;

    		for (r2 = r1 + 1; r2 < prev(num.end(), 1); ++r2)

    			    if (r2 > r1 + 1 && (*r2 == *prev(r2))) continue;

		        	int b = *r2;

		        	int c = target - a - b;

		        	if (binary_search(r2 + 1, num.end(), c))

		        		result.push_back(vector
    
      {a,b,c});

        return result;

3.

3Sum Closest

Total Accepted: 21058 Total Submissions: 78146My Submissions

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

分析： 与上题的不同，上题是等于，这题是接近，看似还是两个循环，再第三个再用循环把最近的找出来就行，可是这样时间复杂度n^3

再分析，与上个题不同的是，上个提相当于1+1+1 三个部分，这个题相当于1+ 2两个部分，把后两个数的和看成一个整体

这样思路就出来了，先排序，然后选一个数，剩下两个左右夹逼（因已经排好序，比要求大就后面的前移，小就前面的后移）时间复杂度n^2,空间复杂度O（1）(是不是对空间来说，没开辟新的数组在存原数组就是1哈哈)（补：算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)）

int threeSumClosest(vector
    
      &num, int target) {

        int result = 0;

        int min_gap = INT_MAX;

        sort(num.begin(),num.end());

        for(auto a = num.begin(); a != prev(num.end(),2); a = upper_bound(a,prev(num.end(),2),*a))

            auto b = next(a);

            auto c = prev(num.end());

            while (b < c)

                int sum = *a + *b + *c;

                int gap = abs(sum - target);

                if (gap < min_gap)

                    result = sum;

                    min_gap = gap;

                if (sum < target) ++b;

                else --c;

        return result;

该算法的改进就是在 if (sum < target) ++b;

                else --c;

处，处理掉对重复元素的检测， 改为b = upper_bound(b,c,*b); c= prev(lower_bound(b,c,*c)); 这样处理后算法，只有常数级别的优化

4.

4Sum
 Total Accepted: 18939 Total Submissions: 88978My SubmissionsGiven an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target  Find all unique quadruplets in the array which gives the sum of target.





Note:

    
     Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
     The solution set must not contain duplicate quadruplets.    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

解： 初始的方法，三个for循环，找第四个数，即使用二分法，也需要n^3*log(n),超时

参考答案后AC的，思路是先缓存两个数的和到集合中，这样空间增大来缩短时间
class Solution {
public:
    vector
       
         > fourSum(vector
        
          &num, int target) { //注意两个> >之间有个空格，否则成了>>右移了
        
       
        if (num.size() < 4) return vector
       
         >();
 //依然考虑少于4的情况
       

        sort(num.begin(),num.end());
       // 排序
        map
       
         > > cache; // int 对应一个 vector ，vector里放的几个pair
         
        
       
        for (int a = 0; a < num.size(); ++a) 
            for (int b = a + 1; b < num.size(); ++b)
                 cache[num[a] + num[b]].push_back(pair
       
        (a,b));
 //把和当做key，对应其两个值，
       
            //注意这里，和为某个值可能有好多对，而map是一对一，这里的push_back可不是map的操作，而是一个和值，对应一个vector,vector的push_back操作，另外vector里存的是元素是pair,每个pair有两个数。同理下面那个cache[key]的size也是vector
                 
        set
       
         > result;
         //set本身有去重效果，其当内有重复key时，自动忽略后来的
       
        for (int c = 2; c < num.size(); ++c)
            //这种int c，也有用的size_t c ;来定义
            for (int  d = c + 1; d < num.size(); ++d)
      //size_t 类型定义在cstddef头文件中，                             
                {
                                            //该文件是C标准库的头文件stddef.h的C++版。它是一个与机器相关
                    int key = target - num[c] - num[d];
        //的unsigned类型，其大小足以保证存储内存中对象的大小。
                    if (cache.find(key) != cache.end())
         //在想用这个，是不是怕数组大小大出int表示范围。
                    {
                        f

做几个leetcode数组题二(二)

3Sum Closest

4Sum