1. LintCode双指针题目（一）（左右指针）

LintCode 228：链表的中点

https://www.lintcode.com/problem/middle-of-linked-list

描述

找到链表的中点

样例

  1. 输入:  1->2->3
  2. 输出: 2    
  3. 样例解释: 返回中间节点的值
  5. 输入:  1->2
  6. 输出: 1    
  7. 样例解释: 如果长度是偶数，则返回中间偏左的节点的值。
  9. 不重新遍历链表的情况下得到中点

解题思路

这题用快慢指针的思路来做。快指针每次移动两个位置，慢指针每次移动一个位置，当快指针移动到链表尾端时，慢指针就是中点。

AC代码

  1. public ListNode middleNode(ListNode head) {
  2.     // 链表为空直接返回null
  3.     if (head == null) {
  4.         return null;
  5.     }
  6.     // 快慢指针，都从head开始
  7.     ListNode fast = head;
  8.     ListNode slow = head;
  10.     while (fast.next != null) {
  11.         // 快指针先走一步
  12.         fast = fast.next;
  13.         // 快指针还能走的话，快慢指针都走一步
  14.         if (fast.next != null) {
  15.             fast = fast.next;
  16.             slow = slow.next;
  17.         }
  18.     }
  19.     // 最后返回slow指针
  20.     return slow;
  21. }

LintCode 539：移动零

https://www.lintcode.com/problem/move-zeroes

描述

给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序
1.必须在原数组上操作
2.最小化操作数

样例

  1. 输入: nums = [0, 1, 0, 3, 12],
  2. 输出: [1, 3, 12, 0, 0].
  4. 输入: nums = [0, 0, 0, 3, 1],
  5. 输出: [3, 1, 0, 0, 0].

解题思路

一个思路是将前面出现的0与后面不是0的数字进行交换，但这样不能保证操作数最小。另一个思路是不用管0，因为0都会移到数组的最后面，所以只要我们把非零元素按原来的顺序挪动到数组的前面，后面设置为0就完成了0的移动。用一个index指针遍历数组，一个位置指针表示不为0的数现在应该移动到的位置，index指针数为0不管，不为0就将其移动至位置指针处，位置指针右移。

AC代码

  1. public void moveZeroes(int[] nums) {
  2.     // write your code here
  3.             // 设置index指针和位置指针初始值，都从0开始
  4.     int index = 0, notZero = 0;
  5.     while (index < nums.length) {
  6.         if (nums[index] != 0) {
  7.             nums[notZero++] = nums[index];
  8.         }
  9.         index++;
  10.     }
  11.     while (notZero < nums.length) {
  12.         nums[notZero++] = 0;
  13.     }
  14. }

LintCode 608：两数和II-输入已排序的数组

https://www.lintcode.com/problem/two-sum-ii-input-array-is-sorted

描述

给定一个已经 按升序排列 的数组，找到两个数使他们加起来的和等于特定数。
函数应该返回这两个数的下标，index1必须小于index2。注意返回的值不是 0-based。
你可以假设每个输入刚好只有一个答案

样例

  1. 输入: nums = [2, 7, 11, 15], target = 9 
  2. 输出: [1, 2]
  4. 输入: nums = [2,3], target = 5
  5. 输出: [1, 2]

解题思路

因为题目保证只有一个答案，所以可以用上篇文字中左右指针的思路，left指针从小的数开始遍历，right指针从大的数开始遍历，两指针指向的和等于target则找到答案；若和大于target则表示两数过大，这时right指针左移（把数变小）；若和小于target则表示两数过小，这时left指针右移（把数变大）。

AC代码

  1. public int[] twoSum(int[] nums, int target) {
  2.     // 设置左右指针
  3.     int left = 0, right = nums.length - 1;
  4.     int[] ans = new int[2];
  5.     while (left < right) {
  6.         int add = nums[left] + nums[right];
  7.         // 和为target表示找到答案
  8.         if (add == target) {
  9.             ans[0] = left + 1;
  10.             ans[1] = right + 1;
  11.             break;
  12.         // 和大于target，right指针左移
  13.         } else if (add > target) {
  14.             right--;
  15.         // 和小于target，left指针右移
  16.         } else {
  17.             left++;
  18.         }
  19.     }
  20.     return ans;
  21. }

LintCode 609：两数和-小于或等于目标值

https://www.lintcode.com/problem/two-sum-less-than-or-equal-to-target

描述

给定一个整数数组，找出这个数组中有多少对的和是小于或等于目标值。返回对数

样例

  1. 输入: nums = [2, 7, 11, 15], target = 24. 
  2. 输出: 5. 
  3. 解释:
  4. 2 + 7 < 24
  5. 2 + 11 < 24
  6. 2 + 15 < 24
  7. 7 + 11 < 24
  8. 7 + 15 < 24
  10. 输入: nums = [1], target = 1. 
  11. 输出: 0.

解题思路

上题的变种，思路一致，稍微处理一下即可。两数之和大于target时，right一直左移直至小于等于，然后此时left指针和right指针之间的数（包括right指针）之和都小于等于target，所以答案个数加上right-left，然后left指针右移。

AC代码

  1. public int twoSum5(int[] nums, int target) {
  2.     // 少于2个数直接返回0
  3.     if (nums.length < 2) {
  4.         return 0;
  5.     }
  6.     // 按升序排序
  7.     Arrays.sort(nums);
  8.     // 设置左右指针
  9.     int left = 0, right = nums.length - 1;
  10.     int ans = 0;
  12.     while (left < right) {
  13.         // 两数和大于target时，right左移直至小于等于target
  14.         while (left < right && nums[left] + nums[right] > target) {
  15.             right--;
  16.         }
  17.         // 此时left指针和right指针之间的数（包括right指针）之和都小于等于target
  18.         if (left < right) {
  19.             ans += right - left;
  20.         }
  21.         // left指针右移
  22.         left++;
  23.     }
  24.     // 返回对数
  25.     return ans;        
  26. }

LintCode 533：两数和的最接近值

https://www.lintcode.com/problem/two-sum-closest-to-target

描述

给定整数数组num，从中找到两个数字使得他们和最接近target，返回两数和与 target 的差的 绝对值。

样例

  1. 输入: nums = [-1, 2, 1, -4] 并且 target = 4
  2. 输出: 1
  3. 解释:
  4. 最小的差距是1，(4 - (2 + 1) = 1).
  6. 输入: nums = [-1, -1, -1, -4] 并且 target = 4
  7. 输出: 6
  8. 解释:
  9. 最小的差距是6，(4 - (- 1 - 1) = 6).

解题思路

还是之前两数和的变种题，用左右指针不断靠近target，更新最小差值即可。

AC代码

  1. public int twoSumClosest(int[] nums, int target) {
  2.     // 按升序排序
  3.     Arrays.sort(nums);
  4.     // 设置左右指针
  5.     int left = 0, right = nums.length - 1;
  6.     int ans = Integer.MAX_VALUE;
  8.     while (left < right) {
  9.         int add = nums[left] + nums[right];
  10.         // 两数和为target时，直接返回0
  11.         if (add == target) {
  12.             return 0;
  13.         }
  14.         // 和小于target，left右移，不断逼近target
  15.         if (add < target) {
  16.             left++;
  17.         }
  18.         // 和大于target，right左移，不断逼近target
  19.         else {
  20.             right--;
  21.         }
  22.         // 比较最小差值
  23.         ans = Math.min(ans, Math.abs(add - target));
  25.     }
  26.     // 返回差值
  27.     return ans;
  28. }

LintCode 443：两数之和 II

https://www.lintcode.com/problem/two-sum-greater-than-target

描述

给一组整数，问能找出多少对整数，他们的和大于一个给定的目标值
O（1）额外空间以及（nlogn)时间复杂度

样例

  1. 输入: [2, 7, 11, 15], target = 24
  2. 输出: 1
  3. 解释: 11 + 15 是唯一的一对
  5. 输入: [1, 1, 1, 1], target = 1
  6. 输出: 6

解题思路

前面小于等于目标值的翻版题目

AC代码

  1. public int twoSum2(int[] nums, int target) {
  2.     // 排序
  3.     int ans = 0;
  4.     Arrays.sort(nums);
  5.     // 设置左右指针
  6.     int left = 0, right = nums.length - 1;
  7.     // 遍历数组
  8.     while (left < right) {        
  9.         int add = nums[left] + nums[right];
  10.         // 和小于target，left指针右移
  11.         if (add <= target) {
  12.             left++;
  13.         } else {
  14.             // 和大于targt，那么从left到right间的数（包括left）与right指针的和都大于target
  15.             // right指针左移
  16.             ans += right - left;
  17.             right--;
  18.         }
  19.     }
  20.     // 返回答案
  21.     return ans;
  22. }

LintCode 461：无序数组K小元素

https://www.lintcode.com/problem/kth-smallest-numbers-in-unsorted-array

描述

找到一个无序数组中第K小的数
O(nlogn)的算法固然可行，但如果你能O(n)解决，那就非常棒了。

样例

  1. 输入: [3, 4, 1, 2, 5], k = 3
  2. 输出: 3
  4. 输入: [1, 1, 1], k = 2
  5. 输出: 1

解题思路

快速选择的思路，跟快排中partition部分一样，随机选择数组中的一个数t，将小于t的数都放至左边，大于t的数放至右边，这样如果左边数的个数大于等于K，则K小元素在左半部分，递归查找左半部分；反之查找右半部分。

AC代码

  1.     public int kthSmallest(int k, int[] nums) {
  2.         // 数组从0开始所以把k-1
  3.         return partition(nums, 0, nums.length - 1, k - 1);
  4.     }
  6.     // 快速选择，和快排中的partition类似
  7.     private int partition(int[] nums, int start, int end, int k) {
  8.         if (start == end) {
  9.             return nums[start];
  10.         }
  12.         // 从左右两端开始
  13.         int left = start, right = end;
  14.         int mid = nums[left + (right - left) / 2];
  16.         while (left < right) {
  17.             // 从左指针扫描找到比mid大的数
  18.             while (left <= right && nums[left] < mid) {
  19.                 left++;
  20.             }
  21.             // 从右指针扫描找到比mid小的数
  22.             while (left <= right && nums[right] > mid) {
  23.                 right--;
  24.             }
  25.             // 进行交换
  26.             if (left <= right) {
  27.                 int tmp = nums[left];
  28.                 nums[left++] = nums[right];
  29.                 nums[right--] = tmp;
  30.             }
  31.         }
  33.         // 进行partition操作后，left 要么等于 right + 1，要么等于right + 2
  34.         // start到right的数小于 mid，left到end的数大于mid
  36.         // 如果right >= k 则表示 左半部分的数至少有 k 个，所以在start 和 right 中查找答案
  37.         if (right >= k && start <= right) {
  38.             return partition(nums, start, right, k);
  39.         }
  40.         // 如果left <= k 则表示 左半部分的数少于 k 个，所以要去left 和 end 中查找答案
  41.         if (left <= k && left <= end) {
  42.             return partition(nums, left, end, k);
  43.         }
  44.         // 上述条件都不满足，则表明当前k的位置便是答案
  45.         return nums[k];
  46.     }

LintCode 382：三角形计数

https://www.lintcode.com/problem/triangle-count

描述

给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻到多少组这样的三个数来组成三角形？

样例

  1. 输入: [3, 4, 6, 7]
  2. 输出: 3
  3. 解释:
  4. 可以组成的是 (3, 4, 6), 
  5.            (3, 6, 7),
  6.            (4, 6, 7)
  8. 输入: [4, 4, 4, 4]
  9. 输出: 4
  10. 解释:
  11. 任何三个数都可以构成三角形
  12. 所以答案为 C(3, 4) = 4

解题思路

前面的443题是在数组中找出有多少组两个数的和大于一个给定的值，而三角形的三条边应满足的条件便是两边之和大于第三边，正好和该题要求的问题一致，所以可以将数组排序，然后从第三个数开始遍历，然后求该数前面的数中能找出多少组两数之和大于它。

AC代码

  1. public int triangleCount(int[] S) {
  2.     // 排序
  3.     Arrays.sort(S);
  4.     int ans = 0;
  5.     // 从第三个数开始枚举
  6.     for (int i = S.length - 1; i > 1 ; i--) {
  7.         // 左指针从0开始，右指针从当前数的前一位开始
  8.         int left = 0, right = i - 1;
  9.         while (left < right) {
  10.             // 两数之和大于答案加一，right指针左移
  11.             if (S[left] + S[right] > S[i]) {
  12.                 ans += right - left;
  13.                 right--;
  14.             } else {
  15.                 // 两数之和小于，left指针右移
  16.                 left++;
  17.             } 
  18.         }
  19.     }
  21.     return ans;        
  22. }

LintCode 144：交错正负数

https://www.lintcode.com/problem/interleaving-positive-and-negative-numbers

描述

给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。
不需要保持正整数或者负整数原来的顺序。完成题目，且不消耗额外的空间。

样例

  1. 输入 : [-1, -2, -3, 4, 5, 6]
  2. 输出 : [-1, 5, -2, 4, -3, 6]
  3. 解释 : 或者任何满足条件的答案

解题思路

一个简单的思路就是把负数集中起来，正数集中起来（可以用快速选择实现，也就是前面题目中的partition部分），然后交替拜访即可。（负数多先放负数，正数多先放正数）

AC代码

  1. public void rerange(int[] A) {
  2.     // 首先将小于0的数移动到左边，大于0的数移动到右边    
  3.     int left = 0, right = A.length - 1;
  4.     while (left < right) {
  5.         while (left < right && A[left] < 0) {
  6.             left++;
  7.         }
  8.         while (left < right && A[right] > 0) {
  9.             right--;
  10.         }
  11.         if (left < right) {
  12.             int tmp = A[left];
  13.             A[left++] = A[right];
  14.             A[right--] = tmp;
  15.         }
  16.     }
  17.     // 因为负数都在左边，正数都在右边，所以隔一个负数就和正数进行一次交换，就能满足正负排列
  18.     // 负数从0开始，正数从最后开始
  19.     int start = 0, end = A.length - 1;
  20.     // 正数个数，left为负数个数
  21.     int posCount = A.length - left;
  22.     // 负数多，那从负数的第二个开始交换，最后队列是负正负正。。。。负正负。
  23.     if (posCount < left) {
  24.         start++;
  25.     // 正数多，从负数的第一个和正数的第二个（从右往左）开始交换，最后队列是正负正负。。。。正负正。
  26.     } else if (posCount > left) {
  27.         end--;
  28.     // 正负一样多，从负数的第二个和正数的第二个（从右往左）开始交换，最后队列是负正负正。。。。负正负正。
  29.     } else {
  30.         start++;
  31.         end--;
  32.     }
  33.     // 交换一个跳一格继续交换，直到交换完成
  34.     while (start < end) {
  35.         int tmp = A[start];
  36.         A[start] = A[end];
  37.         A[end] = tmp;
  38.         start += 2;
  39.         end -= 2;
  40.     }
  42. }