双指针——查找总价格为目标值的两个商品

一.题目描述

LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

二.题目解析 

这个题目非常简单，其实就是判断有没有两个数加起来等于target。

三.算法解析

1.暴力解法

暴力解法的话我们可以枚举出所有的情况，然后判断是否等于target。方法就是先固定一个数，移动另一个数。所以整体时间复杂度为：O(N^2)，空间复杂度为：O(1).

//伪代码
for(i=0; i<n; ++i)
    for(j=i+1; j<n; ++j)
        check(nums[i] + nums[j] == target);

 2.单调性+双指针

题目中已经告诉我们数组是递增的。所以我们可以利用单调性来优化之前的暴力匹配。

我们让两个指针分别指向数组的开始和结尾，然后判断相加之后的结果，再根据单调性选择指针的移动

那么为什么可以这么移动呢？下面给出每种情况的具体分析：

1.left+right > target :

2.left+right<target:

我们来分析时间复杂度：最坏情况下，left和right下一次就会相遇，此时遍历了一遍数组，所以时间复杂度为O(N)，空间复杂度为：O(1).

 四.代码实现

需要注意的是，如果我们直接在循环内返回的话，在leetcode上就会报错：不是所有的路径都有返回值。因为它不能保证你在循环内部就会返回结果，如果结束了循环，外面并没有return语句，此时就会报错。

所以我们就break出去，然后再返回。

这里返回用到了initializer_list+隐式类型转换。

vector<int> twoSum(vector<int>& price, int target)
{
    int left = 0;
    int right = price.size() - 1;
    while (left < right)
    {
        if (price[left] + price[right] > target)
        {
            right--;
        }
        else if (price[left] + price[right] < target)
        {
            left++;
        }
        else
        {
            break;
        }
    }
    return { price[left],price[right] };
}