剑指 Offer 57. 和为s的两个数字

解题思路：双指针

题目给定的条件是数组是按递增排序的

我们可以使用双指针的思路，维护两个指针i,j分别维护数组的首和尾

在i < j的条件范围内，计算nums[i]与nums[j]的和sum

  • sum < target；说明当前两数之和小于target，i指针应该向后移动
  • sum > target；说明当前两数之和大于target，j指针应该向前移动
  • sum == target；因为题目要求输出任意一对符合条件的结果，所以当sum == target返回nums[i]，nums[j]数组即可

代码如下

代码

Java

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         // 双指针
  4.         int i = 0;
  5.         int j = nums.length - 1;
  6.         while(i < j){
  7.             int sum = nums[i] + nums[j];
  8.             if(sum < target){
  9.                 i++;
  10.             }else if(sum > target){
  11.                 j--;
  12.             }else{
  13.                 return new int[]{nums[i],nums[j]};
  14.             }
  15.         }
  16.         return new int[0];
  17.     }
  18. }

复杂度分析

  • 时间复杂度：O(N)

最差的情况，需要遍历整个数组，所以时间复杂度为：O(N)

  • 空间复杂度：O(1)

本题只需要 i，j 两个有限变量，额外空间复杂度为：O(1)