题解 | #和为S的两个数字#

题解一： 暴力
解题思路： 双层循环,在确定第一个值array[i]的情况下，遍历其余所有值，找到相匹配的array[j]，找到即可结束循环
复杂度分析：
时间复杂度： O(n^2)
空间复杂度： O(1)

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum){
        for(int i = 0;i<array.size();i++){//确定第一个数
            for(int j = i+1;j<array.size();j++){
                if(array[i] + array[j] == sum)//判断两数之和是否为S
                {
                    return {array[i],array[j]};//C++11语法，返回结果
                }
            }
        }
        return {};//没有找到，返回空数组
    }
};

题解二：二分查找
解题思路： 利用数组递增排序的特性，满足二分查找条件。
主要思路：

1. 假设当前值为arr[i], 那么第二个数为sum-arr[i]。
2. sum-arr[i] 与 arr[i]的大小分为三种情况：
   a. 如果sum-arr[i] arr[i]相等，那么只需要查找i两侧的值；
   b. 如果sum-arr[i]小于arr[i]，那么在i 的左侧查找sum-arr[i];
   c. 如果sum-arr[i]大于arr[i], 那么在i 的右测查找sum-arr[i];
   示例：
   

复杂度分析：
时间复杂度： O(nlog n )
空间复杂度： O(1)

class Solution {
public:
bool binary_search(const vector<int> &v,int l,int r,int target){
 bool ret = false;
 if(l<0 || l>=v.size() || r<0 || r>=v.size()) return ret;
 while(l<r){
     int mid = (l+r)/2;
     if(v[mid] >= target) r = mid;
     else l = mid+1;
 }
 return v[l] == target;
}
vector<int> construct_ans(int a,int b){
     vector<int> ans = vector<int>{a,b};
     sort(ans.begin(),ans.end());
     return ans;
}
vector<int> FindNumbersWithSum(vector<int> array,int sum){
 for(int i = 0;i<array.size();i++){
     int target = sum - array[i];
     bool ret = false;
     //情况三
     if(target>array[i])
     {
         ret = binary_search(array,i+1,array.size()-1,target);
         if(ret) return construct_ans(array[i], target);
     }
     //情况二
     else if ( target < array[i] )
     {
         ret = binary_search(array,0,i-1,target);
         if(ret) return construct_ans(array[i],target);
     }
     //情况一
     else
     {
         if(i-1>=0 &&  array[i-1] == array[i] || i+1<array.size() && array[i+1] == array[i]) return construct_ans(target,target);
     }
 }
 return {};
}
};

题解三：双指针
解题思路： 利用数组递增排序的特性。
主要思路：

1. 使用left 表示左边指向的值，使用right 表示右边指向的值。
2. (left + right) 与 sum 大小情况 a. （left right）> sum, 则r--， 降低两数之和；
   b. （left + right) < sum, 则l ++，增大两数之和；
   c. (left + right) == sum ,则返回；
   示例：
   
   复杂度分析：
   时间复杂度： O(n)
   空间复杂度： O(1)

   class Solution {
   public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum){
        int left = 0, right = array.size()-1;
        while(left<right)
        {
            if(sum == array[left] + array[right] )//(left + right) == sum ,则返回；
            {
                return vector<int>{array[left],array[right]};
            }
            else if ( sum > array[left] + array[right] )//（left + right) < sum, 则l ++，增大两数之和；
            {
                left++;
            }
            else right--;//（left + right） > sum, 则r--， 降低两数之和；
        }
        return {};
    }
   };

   相关题集:
   反转字符串
   滑动窗口的最大值