167. Two Sum II - Input array is sorted

xiaoxiao2021-02-27  158

题意:给你一个排好升序的数组和一个目标值,让你找出数组中的两个值使得他们的和等于目标值,返回这两个值对应的下标。

思路:如果两两组合来求解的话时间复杂度为O(n*n)。由于数组是升序的,所以可以从两侧同时遍历,根据两侧值的大小来缩小范围,只用了O(n)的时间

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int l = 0,r = numbers.size()-1; while(1) { if(numbers[l]+numbers[r]==target) { vector<int> res{l+1,r+1}; return res; } else { if(numbers[l]+numbers[r]>target) r--; else l++; } } } };

转载请注明原文地址: https://www.6miu.com/read-16171.html

最新回复(0)