1、剑指 Offer 57 - II. 和为s的连续正数序列

1.1 题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：

输入：target = 9 输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]

1.2 思路

  1. 本题是双指针的题目，用左右两个指针来表示连续正整数的范围，需要计算左右两个指针之间的连续正整数之和sum，并与target比较，需要注意左右两个指针只会向右单向遍历；
  2. 左右两个指针的初始化位置：left = 1， right = 2，需要注意左右两个指针不能重合（题目规定至少两个连续正整数）；
  3. 当sum < target时，因为左右两个指针都只向右移动，因此将右指针向右移1位，使sum变大一些；
  4. 当sum > target时，说明以left为起点的连续正整数不存在一个left，使sum == target，因为左右两个指针都只向右移动，因此将左指针向右移动1位，使区间内正整数的数量减1，使sum变小一些；
  5. 当sum == target时，记录此时区间内的数组成的数组并放入res结果中，因为以left为起点的合法解只有一个，需要枚举下一个起点，因此将左指针向右移动1位；

  6. 退出条件是left > right，因为至少包含一个正整数，因此left != right。

    1.3 代码

    1. class Solution {
    2.  public int[][] findContinuousSequence(int target) {
    3.      List<int[]> res = new ArrayList<>();
    4.      int left = 1, right = 2;
    5.      while (left < right) {
    6.          if (getSum(left, right) < target) {
    7.              ++right;
    8.          } else if (getSum(left, right) > target) {
    9.              ++left;
    10.          } else {
    11.              int[] array = new int[right - left + 1];
    12.              for (int i = left; i <= right; ++i) {
    13.                  array[i - left] = i;
    14.              }
    15.              res.add(array);
    16.              ++left;
    17.          }
    18.      }
    19.      return res.toArray(new int[res.size()][]);
    20.  }
    22.  private int getSum(int left, int right) {
    23.      return ((left + right) * (right - left + 1)) >> 1;
    24.  }
    25. }

    2、剑指 Offer 22.链表中倒数第k个节点

    2.1 题目

    输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
    例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
    示例：

    给定一个链表: 1->2->3->4->5, 和 k = 2。返回链表 4->5.

2.2 思路

本题有2种思路：

  1. 第一次遍历链表，求链表长度；第二次遍历链表，结合k求出在哪个下标停止遍历，但需要遍历两次。
  2. 快慢指针。快指针先移动k次，然后快慢指针一起移动，直到快指针为null，此时慢指针指向的节点即倒数第k个节点。

本题采用第二种解法，注意返回的是slow而不是slow.next。

2.3 代码

  1. class Solution {
  2.     public ListNode getKthFromEnd(ListNode head, int k) {
  3.         ListNode fast = head, slow = head;
  4.         for (int i = 0; i < k; ++i) {
  5.             fast = fast.next;
  6.         }
  7.         while (fast != null) {
  8.             fast = fast.next;
  9.             slow = slow.next;
  10.         }
  11.         return slow;
  12.     }
  13. }

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

3.1 题目

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]

3.2 思路

这道题如果用暴力法破解，时间复杂度为O(n2)，会有测试用例不通过。再仔细审题，数组是一个排好序的升序数组，应该利用好这一条件。
本题最佳解法是双指针，左右指针向中间收缩，由于是升序排序的数组，可以通过比较sum值和target的值，调整left和right指针来逼近。时间O(N)，空间O(1)。

3.3 代码

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

4、剑指 Offer 21.调整数组顺序使奇数位于偶数前面

双指针的思路易想，但不容易写对。

4.1 题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：

输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。

4.2 思路

有两种思路：

  1. 用一个双向队列，然后遍历数组num，如果是奇数就放在双向队列的队首，如果是偶数就放在双向队列的队尾。这样做空间复杂度是O(n)，没有做到在数组nums上直接调整，时间复杂度为O(n)；
  2. 用双指针，左右两个指针向中间逼近，左指针找到第一个偶数，右指针直到第一个奇数，然后交换左右指针指向的值，这样做是在数组nums上直接做调整，空间复杂度为O(1)，时间复杂度为O(n)。双指针的思想不难，但是要写正确并不简单，要注意while循环的判断条件，尤其是左右指针做while循环时，虽然在外部while循环有left < right的判断，但是内部的while循环也要加上这个判断，这一点不好想。

    4.3 代码

    双向队列： ```java import java.util.LinkedList;

class Solution { public int[] exchange(int[] nums) { LinkedList list = new LinkedList<>(); for (int num: nums) { if (num % 2 == 0) { list.addLast(num); } else { list.addFirst(num); } } return list.stream().mapToInt(Integer::intValue).toArray(); } }

  1. 双指针：
  2. ```java
  3. class Solution {
  4.     public int[] exchange(int[] nums) {
  5.         int left = 0, right = nums.length - 1;
  6.         while (left < right) {
  7.             while (left < right && (nums[left] & 1) == 1) {
  8.                 ++left;
  9.             }
  10.             while (left < right && (nums[right] & 1) == 0) {
  11.                 --right;
  12.             }
  13.             int tmp = nums[left];
  14.             nums[left] = nums[right];
  15.             nums[right] = tmp;
  16.         }
  17.         return nums;
  18.     }
  19. }

5、11. 盛最多水的容器

这个题很经典。

5.1 题目描述

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
双指针 - 图1

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

5.2 思路

这道题上来我肯定显示o(n2)暴力破解，果然超时…双指针的思路是两个指针从两边向中间移动，不断更新着最大面积，当左右两个指针指向的值，哪个小，哪边的指针就向对方方向移动一格，至于为什么这么移动，有一个推导证明，详情可以见官方解答。

5.3 代码

  1. class Solution {
  2.     public int maxArea(int[] height) {
  3.         int res = 0;
  4.         int left = 0;
  5.         int right = height.length - 1;
  7.         while (left < right)
  8.         {
  9.             int s = Math.min(height[left], height[right]) * (right - left);
  10.             res = Math.max(res, s);
  12.             if (height[left] < height[right])
  13.             {
  14.                 ++left;
  15.             }
  16.             else
  17.             {
  18.                 --right;
  19.             }
  20.         }
  22.         return res;
  23.     }
  24. }