---

算法:雙指針

移動零

定義兩個(gè)指針,slow和fast.用這兩個(gè)指針把整個(gè)數(shù)組分成三塊.
[0,slow]為非零元素,[slow+1,fast-1]為0元素,[fast,num.length]為未處理的元素.
初始情況下slow=-1,fast=0,因?yàn)榇藭r(shí)還沒有對數(shù)組進(jìn)行處理.
用fast遍歷整個(gè)數(shù)組:

• 當(dāng)fast指向的元素不為0時(shí),此時(shí)讓slow++,并交換fast與slow所指向的元素.交換完畢后fast++,繼續(xù)向后處理元素.
• 當(dāng)fast指向的元素為0時(shí),直接fast++.

class Solution {public void moveZeroes(int[] nums) {int slow = -1;int fast = 0;while(fast < nums.length) {if(nums[fast] != 0) {slow++;int tmp = nums[fast];nums[fast] = nums[slow];nums[slow] = tmp;}fast++;}}
}

復(fù)寫零

這道題目如果沒有要求空間復(fù)雜度為O(1)的話,那確實(shí)是簡單題.直接申請一塊數(shù)組,遍歷,然后放進(jìn)去,最后把數(shù)組的引用交換一下就行了.
但是實(shí)際上,這道題還是有點(diǎn)難度的,需要考慮的細(xì)節(jié)情況很多,自己上手寫寫就知道了.

解決這道題,最關(guān)鍵的就是找到數(shù)組中最后一個(gè)要被修改的數(shù),我們可以使用雙指針來找.

• 定義兩個(gè)指針slow和fast并初始化為0.使用slow向后遍歷數(shù)組,當(dāng)slow遇到0時(shí),fast向后移動兩步,slow向后移動一步.當(dāng)slow指向的元素不為零時(shí),fast和slow都向后移動一步.重復(fù)上述過程,直到fast大于數(shù)組長度.
• 循環(huán)結(jié)束后,此時(shí)fast和slow多移動了一步,所以要減掉.在這里還需要考慮fast向后移動了兩步的情況(slow指向了0元素,而此時(shí)fast已經(jīng)位于數(shù)組的最后一個(gè)元素了),判斷一下fast是否越界,如果越界,修改fast的指向,讓fast指向數(shù)組的最后一個(gè)元素,因?yàn)檫@時(shí)slow指向的元素肯定是0,所以我們可以將數(shù)組的最后一位修改成0,之后讓slow和fast向前移動一位.
• 當(dāng)程序運(yùn)行到這里時(shí),所有的特殊情況我們就都處理完了.接下來就是簡單的移動和賦值了,這里就不再贅述了~

class Solution {public void duplicateZeros(int[] arr) {int fast = 0;int slow = 0;while(fast < arr.length) {if(arr[slow] == 0) fast++;fast++;slow++;}--slow;--fast;if(fast == arr.length) {fast = arr.length-1;arr[fast--] = arr[slow--];}while(slow >= 0) {if(arr[slow] == 0) {arr[fast--] = 0;}arr[fast--] = arr[slow--];}}
}

也可以看看宮水三葉大佬寫的代碼,大佬在力扣上寫了題解,可以去看看.

class Solution {public void duplicateZeros(int[] arr) {int n = arr.length, i = 0, j = 0;while (j < n) {if (arr[i] == 0) j++;i++; j++;}i--; j--;while (i >= 0) {if (j < n) arr[j] = arr[i];if (arr[i] == 0 && --j >= 0) arr[j] = 0;i--; j--;}}
}作者：宮水三葉
鏈接：https://leetcode.cn/problems/duplicate-zeros/solutions/1607062/by-ac_oier-zivq/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

快樂數(shù)

這道題條件給的很全,如果題目沒給"重復(fù)這個(gè)過程直到這個(gè)數(shù)變?yōu)?,也可能是無限循環(huán)但始終變不到1"這個(gè)條件.
那么就需要好好的想一想了,上面的條件是可以證明出來的.運(yùn)用到了數(shù)學(xué)上的思想"鴿巢原理",這個(gè)放到最后再寫吧,先寫題解~

• "將一個(gè)正整數(shù)替換為它每個(gè)位置上的數(shù)字的平方和"這個(gè)我們可以把它寫成一個(gè)方法,方便調(diào)用,寫法也很簡單,這里就不寫了.
• 這道題最核心的地方，在于你怎么判斷它無限循環(huán)永遠(yuǎn)到不了1，我們可以使用雙指針來幫助我們判斷，如果你之前做過環(huán)形鏈表，那么就很容易想到。
• 定義兩個(gè)指針slow和fast，并初始化為n，首先讓fast先走一步(做一次替換,因?yàn)橹蟮难h(huán)內(nèi)需要判斷fast和slow是否相等).
• 緊接著進(jìn)入循環(huán),循環(huán)條件為fast != 1 || fun(fast) != 1,因?yàn)橹骹ast要一次向后走兩步,所以fast的當(dāng)前值和fast的下一個(gè)值都要判斷.循環(huán)內(nèi)如果fast與slow相等,說明有環(huán)了,直接return false.如果不相等,slow向后走一步,fast向后走兩步.
• 如果fast走著走著跳出了循環(huán)(表示fast可以被替換成1),此時(shí)直接return true.

class Solution {public static int fun(int n) {int sum = 0;while(n > 0) {int tmp = n%10;sum += tmp*tmp;n/=10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = fun(n);while(fast != 1 || fun(fast) != 1) {if(fast == slow) {return false;}fast = fun(fun(fast));slow = fun(slow);}return true;}
}

鴿巢原理講解:
以下是不太嚴(yán)謹(jǐn)?shù)淖C明~
舉個(gè)例子,比如說n = 9999999999.
n經(jīng)過一次變換之后n = 9^2*10 = 810.也就是說變換的區(qū)間就在[1,810]這個(gè)范圍內(nèi).
如果我們將n變換810次,最差的情況就是[1,810]內(nèi)所有的數(shù)都出現(xiàn)了一次.如果n在此基礎(chǔ)上再次變換,那么這個(gè)數(shù)肯定就會落在這個(gè)區(qū)間內(nèi),此時(shí)就形成了環(huán)路.

盛最多水的容器

寫這道題時(shí),我們就要分析分析了.
設(shè)盛水容量為v,底部變長為s,高為h.左指針為left指向最左邊,右指針為right指向最右邊,兩個(gè)指針向?qū)Ψ揭苿?
根據(jù)題意,我們可得:

• v = s * h;
• s = right - left;
• h = min(left,right);
  當(dāng)我們移動指向的最高的線的指針時(shí),有以下兩種情況:
• s 減小(兩指針之間的距離變短了), 移動后指針的指向的線高于移動前的線,h 不變(因?yàn)槭⑺嗌偃Q于最低的線),那么 v 減小
• s 減小,移動后指針的指向的線低于移動前的線,h 不變或減小(因?yàn)槭⑺嗌偃Q于最低的線,移動后的指針指向的線可能比另一個(gè)指針指向的線短,也可能在移動后仍然比另一個(gè)指針指向的線長),那么 v 減小.
  可以看到,當(dāng)我們移動指向的最高的線的指針時(shí),v并不會增大.

當(dāng)我們移動指向的最低的線的指針時(shí),有以下兩種情況:

• s 減小(兩指針之間的距離變短了), 移動后指針的指向的線高于移動前的線,h 增大(因?yàn)槭⑺嗌偃Q于最低的線),那么 v 的變化不能確定.
• s 減小,移動后指針的指向的線低于移動前的線,h 減小(因?yàn)槭⑺嗌偃Q于最低的線),那么 v 減小.

綜合上述分析,我們可以得到,只有在移動指向的最低的線的指針,并且移動后,指針的指向的線,高于移動前的線時(shí),v才有可能變大.

有了以上的分析,代碼就很好寫啦~

class Solution {public int maxArea(int[] height) {int left = 0;int right = height.length - 1;int v = 0;while(left < right) {int s = Math.min(height[left],height[right]);int tmp = s*(right-left);if(tmp > v) {v = tmp; }if(height[left] == s) {left++;} else {right--;}}return v;}
}

有效三角形的個(gè)數(shù)

先給數(shù)組排個(gè)序.
從后向前固定一個(gè)i值(循環(huán)1),當(dāng)left小于right時(shí)(循環(huán)2),讓left和right指向的數(shù)相加,判斷是否大于i指向的數(shù).

• 大于i,讓sum+=right-left; right–;
• 小于或等于i,讓left向右移.
  

class Solution {public int triangleNumber(int[] nums) {int left =0;int right = 0;Arrays.sort(nums);int sum = 0;for(int i=nums.length - 1;i >= 2;i--) {right = i-1;left = 0;while(left < right) {if(nums[left]+nums[right] > nums[i]) {sum += right -left;right--;} else {left++;}}}return sum;}
}

查找總價(jià)格為目標(biāo)值的兩個(gè)商品

感覺沒什么可說的~

class Solution {public int[] twoSum(int[] price, int target) {int left = 0;int right = price.length - 1;while(left < right) {if(price[left] + price[right] > target) {right--;} else if(price[left] + price[right] < target) {left++;} else{return new int[]{price[left],price[right]};}}return null;}
}

三數(shù)之和

自己寫的代碼,在最開始new ArrayList<List<Integer>>()的時(shí)候不會new,忘了.(后來發(fā)現(xiàn)不用這么麻煩寫e)
還有我最開始是在最內(nèi)層循環(huán)里面使用了list.contains(list2),然后超時(shí)了qwq.
后來去看題解,發(fā)現(xiàn)還能這樣去重!
改了改就成現(xiàn)在這樣了,雖然效率還是很低就是了.

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<List<Integer>>();Arrays.sort(nums);int left = 0;int right = nums.length - 1;for(int i = nums.length-1; i >= 2; i--) {if(i < nums.length - 1 && nums[i] == nums[i+1]) continue;right = i - 1;left = 0;while(left < right) {if(right != i-1 && right >= left +1 && nums[right] == nums[right+1]) {right--;continue;}int tmp = nums[left] + nums[right] + nums[i];if(tmp > 0) {right--;} else if(tmp < 0) {left++;} else {ArrayList<Integer> list2 = new ArrayList<>();list2.add(nums[left]); list2.add(nums[right]); list2.add(nums[i]); list.add(list2);right--;}}}return list;}
}

看了講解后:

1. List<List<Integer>> list = new ArrayList<List<Integer>>();其實(shí)可以寫成
   List<List<Integer>> list = new ArrayList<>(); < >里面可以啥都不寫.
2. 當(dāng)num[i]<0時(shí),此時(shí)最大的數(shù)都小于0了,肯定三數(shù)之和就不可能等于0了,直接跳過.
3. 第一次見還能這樣寫: list.add(new ArrayList(Arrays.asList(nums[left],nums[right],nums[i])));
4. 當(dāng)三數(shù)和為0時(shí),left和right可以都移動一步(我寫的只有right移動一步).
5. 當(dāng)三數(shù)和為0并且left和right移動后,此時(shí)就可以開始去重了,不必在內(nèi)層循環(huán)用if和continue去重(這樣多判斷了right != i-1),而且我只對right去重了,left還是要經(jīng)過整個(gè)循環(huán)emmm,雖然也達(dá)到了去重的效果(歪打正著,我當(dāng)時(shí)還在想為啥if和continue不能換成while?被自己蠢哭了qwq).其實(shí)沒必要,直接同時(shí)去重就OK了.

雖然自己第一次寫的代碼能通過,但是可優(yōu)化的地方還有很多.沒有大佬寫的代碼優(yōu)雅~

以下是改后的代碼:

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);int left = 0;int right = nums.length - 1;for (int i = nums.length - 1; i >= 2; i--) {if (nums[i] < 0)break;if (i < nums.length - 1 && nums[i] == nums[i + 1])continue;right = i - 1;left = 0;while (left < right) {int tmp = nums[left] + nums[right] + nums[i];if (tmp > 0) {right--;} else if (tmp < 0) {left++;} else {list.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[right],nums[i])));right--;left++;while (right > left && nums[right] == nums[right + 1]) {right--;}while (right > left && nums[left] == nums[left - 1]) {left++;}}}}return list;}
}

四數(shù)之和

自己寫出來的,中間改了好幾次,終于過了~
跟上一題很像.
自己寫的代碼:

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);if (nums[nums.length - 1] < 0 && target > 0) {return list;}for (int i = 0; i < nums.length - 3; i++) {if (nums[i] > 0 && target <= 0) {break;}if (i != 0) {while (i < nums.length - 3 && nums[i] == nums[i - 1]) {i++;}}for (int j = i + 1; j < nums.length - 2; j++) {if (j != i + 1) {while (j < nums.length - 2 && nums[j] == nums[j - 1]) {j++;}}int left = j + 1;int right = nums.length - 1;while (left < right) {long sum = nums[left] + nums[right] + nums[i] + nums[j];if (sum > target) {right--;} else if (sum < target) {left++;} else {list.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));left++;right--;while (left < right && nums[left] == nums[left - 1]) {left++;}while (left < right && nums[right] == nums[right + 1]) {right--;}}}}}return list;}
}

看了講解后:

• 去重操作可以放在最后寫

改后代碼:

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);if (nums[nums.length - 1] < 0 && target > 0) {return list;}for (int i = 0; i < nums.length - 3;) {if (nums[i] > 0 && target <= 0) {break;}for (int j = i + 1; j < nums.length - 2;) {int left = j + 1;int right = nums.length - 1;while (left < right) {int sum = nums[left] + nums[right] + nums[i] + nums[j];if (sum > target) {right--;} else if (sum < target) {left++;} else {list.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));left++;right--;while (left < right && nums[left] == nums[left - 1]) {left++;}while (left < right && nums[right] == nums[right + 1]) {right--;}}}j++;while (j < nums.length - 2 && nums[j] == nums[j - 1]) {j++;}}i++;while (i < nums.length - 3 && nums[i] == nums[i - 1]) {i++;}}return list;}
}

總結(jié)

使用雙指針:

1. 一般是在數(shù)組中使用,通常需要對數(shù)組進(jìn)行排序.
2. 數(shù)據(jù)要有單調(diào)性.
3. 使用雙指針可以把時(shí)間復(fù)雜度降一維.O(n³)變O(n²);