hot100之双指针

移动0(283)

先看代码

1. class Solution {
2.     public void moveZeroes(int[] nums) {
3.         int idx0 = 0;
4.         for (int idx = 0; idx < nums.length; idx++){
5.             if(nums[idx] != 0){
6.                 int temp = nums[idx0];
7.                 nums[idx0] = nums[idx];
8.                 nums[idx] = temp;
9.                 idx0++;
10.             }
11.         }
12.     }
13. }

复制代码

• 分析
  

由于仅当 nums[idx] == 0 时 idx0和idx间距会扩大   即有idx0 ~idx 间都为0
idx0用于记录0的起始位置, idx 向前移动发现非0 填入idx0  idx0 向右移动

• 感悟
  

双指针通过停一动一, 将两次遍历融合在一次遍历中, 同时维护两个指针, 处理两个数据
盛最多水的容器(011)

先看代码

1. class Solution {
2.     public int maxArea(int[] height) {
3.         int res = 0;
4.         int lef = 0;
5.         int rig = height.length - 1;
6.         while (lef < rig){
7.             int area = (rig - lef) * Math.min(height[lef], height[rig]);
8.             res = Math.max(res, area);
9.             if (height[lef] < height[rig]){
10.                 lef++;
11.             }else rig--;
12.         }
13.         return res;
14.     }
15. }

复制代码

• 分析
  

容器盛最多水由短板决定, 显然在相同短板下容器越宽越好 所以让左右板从最边缘开始
增大容器容量只能通过寻找更优最短板(lef++ OR rig--), 此时的 trade off 就是容器变窄

• 感悟
  

双指针技巧特别适合需要同时考虑多个值的处理场景
三数之和(015)

先看代码

1. class Solution {
2.     public List<List<Integer>> threeSum(int[] nums) {
3.         List<List<Integer>> res = new ArrayList<>();
4.         int n = nums.length;
5.         Arrays.sort(nums);
6.         for (int i = 0; i < n; i++){
7.             if (nums[i] > 0)     break;
8.             if (i > 0 && nums[i] == nums[i-1]) continue;
10.             int lef = i+1;
11.             int rig = n-1;
12.             while (lef < rig){
13.                 int sum = nums[i] + nums[lef] + nums[rig];
14.                 if(sum == 0){
15.                     res.add(Arrays.asList(nums[i], nums[lef], nums[rig]));
16.                     while (lef < rig && nums[lef] == nums[lef+1])  lef++;
17.                     while (lef < rig && nums[rig] == nums[rig-1])  rig--;
18.                     lef++;
19.                     rig--;
20.                 }
21.                 else if(sum < 0) lef++;
22.                 else if(sum > 0) rig--;
23.             }
24.         }
25.         return res;
26.     }
27. }

复制代码

• 分析
  

分解问题成定一找二 寻找 nums + nums[j]  = - nums[k]  且 k < i, j < n-1
nums[k] 要和 (nums + nums[j]) 为异号, 且当 nums[k] > 0 时结束

k < i , j < n-1 可行性分析
因为 nums + nums [j] + nums[k]   i, j, k 可相互替换
k 枚举了所有 nums OR nums[j] OR nums[k]  < 0的情况

先通过 sort 对原数组排序 →(方便去重 |  便于 nums[k] > 0 时结束 )

• 感悟
  

写完了两数之和, 第一感觉是要以nums[k]作target , 取nums + nums[j]作两数之和
但分析之后发现 还是用了二分

时间复杂度: 双指针O(n*logn + n²/2 ), hash O(n² + k(n))
双指针有 n²/2 因为只枚举小于0情况, 由实际动态浮动 , 这里就先取个2
k(n)指哈希计算、解决哈希冲突, 及哈希扩容
空间复杂度: 双指针O(1), hash O(n² → 利用hashset去重)   双指针在res中操作, 而hash 还要维护set
另外, hash代码实现比较麻烦   orz

接雨水(042)

先看代码

1. class Solution {
2.     public int trap(int[] height) {
3.         int res = 0;
4.         int lef = 0;
5.         int rig = height.length-1;
6.         int preMax = 0;
7.         int sufMax = 0;
8.         while (lef < rig){
9.             preMax = Math.max(preMax, height[lef]);
10.             sufMax = Math.max(sufMax, height[rig]);
11.             res += preMax > sufMax ? sufMax - height[rig--] : preMax - height[lef++];
12.         }
13.         return res;
14.     }
15. }

复制代码

• 分析
  

通过维护全局两侧最高板, 采用了盛最多水的容器(011)的做法 寻找最优短板
对遍历到的块的接水量进行计算

• 感悟
  

暂无

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！