和为s的两个数字

---

题目：

题解：

1、双指针

• 解题思路：

  1. 计算和 s = nums[i] + nums[j]；
  2. 若 s > target ，则指针 j 向左移动，即执行 j = j - 1；
  3. 若 s < target，则指针 i 向右移动，即执行 i = i + 1；
  4. 若 s = target ，立即返回数组 [nums[i], nums[j]]；

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为数组 nums 的长度；双指针共同线性遍历整个数组。
  • 空间复杂度 O(1) ： 变量 i, j 使用常数大小的额外空间。

• 代码：

  class Solution {
      public int[] twoSum(int[] nums, int target) {
          int i = 0;
          int j = nums.length - 1;
          // 提前把大于target的排除，也可防止nums[i] + nums[j]时溢出
          while (i < j && target < nums[j]) {
              j--;
          }
          while (i < j) {
              // 这个s很重要，如果这样写，后面判断都得计算nums[i] + nums[j]，效率将会降低
              int s = nums[i] + nums[j];
              if (s > target){
                  j--;
              }else if (s < target){
                  i++;
              }else return new int[] {nums[i],nums[j]};// 不在前面定义，可以动态的节省空间
          }
          return new int[0];
      }
  }