剑指offer——面试题41-2：和为S的两个数字

力扣

双指针算法

Python

class Solution:
    def twoSum(self, price: List[int], target: int) -> List[int]:
        if len(price) < 2:
            return []
        l, r = 0, len(price) - 1
        while l < r:
            if price[l] + price[r] == target:
                return [price[l], price[r]]
            elif price[l] + price[r] < target:
                l += 1
            else:
                r -= 1
        return []

Java

class Solution {
    public int[] twoSum(int[] price, int target) {
        int left = 0, right = price.length - 1;
        while (price[left] + price[right] != target) {
            if (price[left] + price[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return new int[]{price[left], price[right]};
    }
}

##Solution1:
算法：双指针的经典用法

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int low = 0, high = array.size() - 1;
        vector<int> res;
        while(low < high){
            if(array[low] + array[high] > sum)
                high--;
            else if(array[low] + array[high] < sum)
                low++;
            else {
                if(res.size() == 2 && array[low] * array[high] < res[0] * res[1]) {
                    res[0] = array[low];
                    res[1] = array[high];
                }
                if(res.size() == 0) {
                    res.push_back(array[low]);
                    res.push_back(array[high]);
                }
                low++;
            }
        }
        return res;
    }
};

##Solution2:
20180906重做

class Solution { // 双指针算法
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if (array.size() < 2) return {};
        if (array.size() == 2) {
            if (array[0] + array[1] == sum)
                return array;
            else return {};
        }
        vector<int> res(2, 0);
        int multi_res = INT_MAX;
        int left = 0, right = array.size() - 1;
        while (left < right) {
            if (array[left] + array[right] < sum)
                left++;
            else if (array[left] + array[right] > sum)
                right--;
            else { // 和恰好为sum
                if (array[left] * array[right] < multi_res) {
                    multi_res = array[left] * array[right];
                    res[0] = array[left];
                    res[1] = array[right];
                }
                left++; right--;
            }
        }
        if (!res[0] && !res[1])
            return {};
        return res;
    }
};