题目链接:LCR 179. 查找总价格为目标值的两个商品 - 力扣(LeetCode)
如果这道题采用双重循环来找到和为目标值的两个数,时间复杂度高,效率低。
题上说明数组按照升序排序,因此我们可以利用这个性质用双指针解决。
如图,因为8+66>61,而8~66中间的都比8大,因此和66相加只会更加大于61,所以指向66的指针要左移
然后8+52<61,那就把指向8的指针右移。
重复以上步骤就能快速找到和为目标值的两个数。
代码:
public int[] twoSum(int[] price, int target) {
int left = 0,right = price.length - 1;
int[] arr = new int[2];
while(left < right){
if(price[left] + price[right] == target){
arr[0] = price[left];
arr[1] = price[right];
break;
}else if(price[left] + price[right] > target){
right--;
}else{
left++;
}
}
return arr;
}