數(shù)組中的問題其實最常見
如：排序（選擇排序、插入排序汰现、歸并排序挂谍、快速排序）、查找（二分查找法）瞎饲、數(shù)據(jù)結(jié)構(gòu)（棧口叙、隊列、堆）
注意：
1企软、如果沒有解庐扫，返回什么饭望？
2仗哨、如果有多個解，返回哪個解铅辞？若要返回任意解厌漂，順序有要求嗎？
3斟珊、字符串相關(guān)：空串如何看苇倡、大小寫問題、字符的取值范圍
ps：例題選自LeetCode
一、從二分查找法看如何寫出正確的程序
思想：保證循環(huán)的循環(huán)不變量
明確變量的含義
整型溢出解決方法：由(l+r)/2 修改為l+(r-l)/2
二旨椒、移動晓褪、移除數(shù)組中特定元素
算法思想：遍歷一遍數(shù)組，將遍歷到的不為0的元素综慎，移到數(shù)組前方標(biāo)記位置涣仿。
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)示惊。
題目：給定一個數(shù)組 nums好港，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序米罚。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
public class MoveZeros<Item> {
public static int[] moveZeroes(int[] nums) {
/**
* 1钧汹、創(chuàng)建一個新的數(shù)組 newNums
* 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
* 內(nèi)存消耗：40 MB, 在所有 Java 提交中擊敗了5.62% 的用戶
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：O(n)
*/
int[] newNums = new int[nums.length];
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0){
newNums[j] = nums[i];
j++;
}
}
for (int i = j; i < nums.length; i++) {
newNums[i] = 0;
}
return newNums;
/**
* 2录择、最優(yōu)解——交換位置拔莱，發(fā)現(xiàn)不為0元素，移到前方隘竭，注意全為非0時k與i辨宠。
* 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
* 內(nèi)存消耗：39.6 MB, 在所有 Java 提交中擊敗了5.62% 的用戶
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：O(1)
*/
int k = 0; // 記錄當(dāng)前不為0的位置 ☆
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0 ){
if (k != i){ // 如果k==i，則只需要使k+1即可货裹。
nums[k] = nums[i];
nums[i] = 0; // 交換操作嗤形，這里為了簡單直接令為0了。
}
k++;
}
}
return nums;
/**
* 3弧圆、遍歷當(dāng)前位置之后的元素赋兵，不為0則移到當(dāng)前位置∩υぃ——比較復(fù)雜
* 執(zhí)行用時：5 ms, 在所有 Java 提交中擊敗了5.00% 的用戶
* 內(nèi)存消耗：40 MB, 在所有 Java 提交中擊敗了5.62% 的用戶
* 時間復(fù)雜度：O(n^2)
* 空間復(fù)雜度：O(1)
*/
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0 && i < nums.length-1) {
int j = i+1;
while (nums[j] == 0 && j < nums.length-1){
j++;
}
if (j < nums.length && nums[j] !=0) {
nums[i] = nums[j];
nums[j] = 0;
}
}
}
return nums;
}
public static void main(String[] args) {
int[] m = {1,4,6,0,2,6,0,0,7};
for (int i = 0; i < moveZeroes(m).length; i++) {
System.out.println(moveZeroes(m)[i]);
}
}
}
題目：給你一個數(shù)組 nums 和一個值 val霹期，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度拯田。
要求：
1历造、不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組船庇。
2吭产、元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素鸭轮。
示例 :
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 2臣淤。
你不需要考慮數(shù)組中超出新長度后面的元素是什么。
- 算法思想同上題283中方法二一樣窃爷。
/** 刪除數(shù)組中值為val的元素邑蒋，并返回該數(shù)組姓蜂。
* 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
* 內(nèi)存消耗：38.4 MB, 在所有 Java 提交中擊敗了5.68% 的用戶
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：O(1)
*/
public int removeElement(int[] nums, int val) {
int k = 0; // 數(shù)組中前k個元素不為val
int tem = 0; // 交換位置中間變量
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val ){
if (i != k){
tem = nums[k];
nums[k] = nums[i];
nums[i] = tem;
}
k++;
}
}
return k;
}
題目：給定一個排序數(shù)組，你需要在 原地 刪除重復(fù)出現(xiàn)的元素医吊，使得每個元素只出現(xiàn)一次钱慢，返回移除后數(shù)組的新長度。
要求：不要使用額外的數(shù)組空間卿堂，你必須在 原地 修改輸入數(shù)組滩字，并在使用 O(1) 額外空間的條件下完成。
示例 1:
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2御吞。
你不需要考慮數(shù)組中超出新長度后面的元素麦箍。
算法思想：遍歷一遍數(shù)組，記錄遍歷到的上一元素值X標(biāo)記其位置陶珠，對比當(dāng)前元素挟裂，若不相等，則將該元素移到數(shù)組前方標(biāo)記位置揍诽。更新X及標(biāo)記的位置诀蓉。
// 執(zhí)行用時：1 ms, 在所有 Java 提交中擊敗了98.16% 的用戶
// 內(nèi)存消耗：40.3 MB, 在所有 Java 提交中擊敗了96.86% 的用戶
public int removeDuplicates(int[] nums) {
int lastNumber = 0; // 記錄當(dāng)前無重復(fù)值的位置
for(int i = 0;i < nums.length;i++){
if(nums[i] != nums[lastNumber]){
lastNumber ++; // 發(fā)現(xiàn)新元素，位置加一
nums[lastNumber] = nums[i]; // 賦值
}
}
return lastNumber+1;
}
- 在c++中暑脆，可以使用 freq[256] 來判斷元素出現(xiàn)頻率渠啤。
題目：
給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素添吗，使得每個元素最多出現(xiàn)兩次沥曹，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間碟联，你必須在原地修改輸入數(shù)組**并在使用 O(1) 額外空間的條件下完成妓美。
算法思想：遍歷一遍數(shù)組，記錄遍歷到的上一元素值X標(biāo)記其位置鲤孵，記錄出現(xiàn)次數(shù)壶栋。對比當(dāng)前元素，若相等普监，判斷出現(xiàn)次數(shù)time贵试，小于等于2次，或不相等凯正。則將該元素移到數(shù)組前方標(biāo)記位置毙玻，更新X及標(biāo)記的位置。
// 執(zhí)行用時：1 ms, 在所有 Java 提交中擊敗了97.38% 的用戶
// 內(nèi)存消耗：38.8 MB, 在所有 Java 提交中擊敗了80.16% 的用戶
public int removeDuplicates(int[] nums) {
int lastNumber = 0; // 上一個元素位置漆际，從第一個開始淆珊。
int time = 1; // 元素出現(xiàn)次數(shù)躯概，第一個元素已有拒迅，所以初始是1次
for(int i = 1;i < nums.length; i++){ // i 從第二個開始
if(nums[i] == nums[lastNumber]){
time++;
if(time <= 2){
lastNumber++;
nums[lastNumber] = nums[i];
}
}else{
lastNumber++;
nums[lastNumber] = nums[i];
time = 1;
}
}
return lastNumber + 1;
}
三、計數(shù)排序慈迈、歸并排序
題目：給定一個包含紅色擂找、白色和藍(lán)色戳吝，一共 n 個元素的數(shù)組，原地對它們進(jìn)行排序贯涎，使得相同顏色的元素相鄰听哭，并按照紅色、白色塘雳、藍(lán)色順序排列陆盘。
此題中，我們使用整數(shù) 0败明、 1 和 2 分別表示紅色隘马、白色和藍(lán)色。
注意:
不能使用代碼庫中的排序函數(shù)來解決這道題妻顶。
示例:
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
進(jìn)階： 一個直觀的解決方案是使用計數(shù)排序的兩趟掃描算法酸员。
首先，迭代計算出0讳嘱、1 和 2 元素的個數(shù)幔嗦，然后按照0、1沥潭、2的排序邀泉，重寫當(dāng)前數(shù)組。
你能想出一個僅使用常數(shù)空間的一趟掃描算法嗎钝鸽？
算法思想：三路快排（最優(yōu)）
1呼渣、遍歷出0、1寞埠、2的個數(shù)屁置，依次給數(shù)組賦值
/**
* 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
* 內(nèi)存消耗：38.1 MB, 在所有 Java 提交中擊敗了6.67% 的用戶
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：O(n)
*/
int[] count = new int[3];
for (int i = 0; i < nums.length; i++) {
if (nums[i]>=0 && nums[i]<3){
count[nums[i]]++; // count中下標(biāo)對應(yīng)值加1
}
}
// 按照count中的統(tǒng)計結(jié)果，給nums數(shù)組賦值仁连。
int k = 0;
for (int i = 0; i < 3;i++){
for (int j = 0; j < count[i]; j++,k++) {
nums[k]=i;
}
}
2蓝角、三路快排
/**
* 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
* 內(nèi)存消耗：38.2 MB, 在所有 Java 提交中擊敗了6.67% 的用戶
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：O(1)
*/
int zero = -1;
int two = nums.length;
for (int i = 0;i<two;){
if (nums[i] == 0){
zero++;
nums[zero] = nums[i];
if(zero != i){
nums[i] = 1;
}
i++;
}else if (nums[i] == 1){
i++;
}else if (nums[i] == 2){
two--;
nums[i] = nums[two];
nums[two] = 2;
}else {
System.out.println("請輸入只有0、1饭冬、2的數(shù)字使鹅！");
return;
}
}
題目：
給你兩個有序整數(shù)數(shù)組 nums1 和 nums2，請你將 nums2 合并到 nums1 中昌抠，使 nums1 成為一個有序數(shù)組患朱。
說明:
初始化 nums1 和 nums2 的元素數(shù)量分別為 m 和 n 。
你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素炊苫。
示例:
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]
算法思想：從后往前排——不借用輔助空間裁厅，在nums1上交換元素實現(xiàn)冰沙。
（1）一次歸并排序——借用一個輔助數(shù)組，從前往后排
public static void merge(int[] nums1, int m, int[] nums2, int n) {
/**
* 執(zhí)行用時：14 ms, 在所有 Java 提交中擊敗了5.29% 的用戶
* 內(nèi)存消耗：39.9 MB, 在所有 Java 提交中擊敗了5.06% 的用戶
* 時間復(fù)雜度：O(n+m) 空間復(fù)雜度：O(n)
*/
int[] p = new int[nums1.length]; // 存儲最終結(jié)果的輔助數(shù)組
int a = 0;
int b = 0;
for (int i = 0; i < m+n; i++){
if(a == m){
p[i] = nums2[b];
b++;
}else if(b == n){
p[i] = nums1[a];
a++;
}else if (a < m || b<n){
if (nums1[a] <= nums2[b]){
p[i] = nums1[a];
a++;
}else if(nums1[a]>nums2[b]){
p[i] = nums2[b];
b++;
}
}
}
for (int i = 0;i<nums1.length;i++){
nums1[i] = p[i];
System.out.println(nums1[i]);
}
}
（2）從后往前排——不借用輔助空間执虹，在nums1上交換元素實現(xiàn)拓挥。
☆☆☆☆☆☆最優(yōu)☆☆☆☆☆☆
public static void merge(int[] nums1, int m, int[] nums2, int n) {
/**
* 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
* 內(nèi)存消耗：40 MB, 在所有 Java 提交中擊敗了5.06% 的用戶
* 時間復(fù)雜度：O(m+n) 空間復(fù)雜度O(1)
*/
int c = m-1;
int d = n-1;
for (int i = m + n - 1; i >= 0; i--) {
if(c==-1){
nums1[i] = nums2[d];
d--;
}else if(d==-1){
nums1[i] = nums1[c];
c--;
}else {
if (nums1[c]>nums2[d] ){
nums1[i] = nums1[c];
c--;
}else if(nums1[c] <= nums2[d]){
nums1[i] = nums2[d];
d--;
}
}
}
（3）用排序函數(shù)排序，忽略了數(shù)組有序的條件袋励。
public static void merge(int[] nums1, int m, int[] nums2, int n) {
/**
* 執(zhí)行用時：1 ms, 在所有 Java 提交中擊敗了23.72% 的用戶
* 內(nèi)存消耗：39.8 MB, 在所有 Java 提交中擊敗了5.06% 的用戶
*/
System.arraycopy(nums2, 0, nums1, m, n);
Arrays.sort(nums1);
}
題目：
在未排序的數(shù)組中找到第 k 個最大的元素侥啤。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素茬故，而不是第 k 個不同的元素盖灸。假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度磺芭。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
算法思想：先排序（堆排序赁炎、快排 O(nlogn)），在找到第K大的元素徘跪。
四甘邀、對撞指針——尋找兩數(shù)和、回文串垮庐、字符串倒序松邪、元素翻轉(zhuǎn)——雙索引技術(shù)
題目：給定一個已按照升序排列 的有序數(shù)組，找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)哨查。
函數(shù)應(yīng)該返回這兩個下標(biāo)值 index1 和 index2逗抑，其中 index1 必須小于 index2。
說明:
返回的下標(biāo)值（index1 和 index2）不是從零開始的寒亥。
你可以假設(shè)每個輸入只對應(yīng)唯一的答案邮府，而且你不可以重復(fù)使用相同的元素。
示例:
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 溉奕。因此 index1 = 1, index2 = 2 褂傀。
算法思路：設(shè)置左右兩個指針，如果相加大于目標(biāo)值加勤，右指針前進(jìn)一位仙辟；如果相加小于目標(biāo)值，左指針前進(jìn)一位鳄梅。（不會錯過目標(biāo)值）
思路2：雙重循環(huán)暴力破解叠国，思路簡單，效率不高戴尸。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] a = new int[2];
for(int i = 0,j=numbers.length -1 ;i < numbers.length && j > i ; ){
if(numbers[i] + numbers[j] == target){
a[0] = i+1;
a[1] = j+1;
break;
}
else if(numbers[i] + numbers[j] > target){
j--;
}else if(numbers[i] + numbers[j] < target){
i++;
}
}
// 思路二粟焊，雙重循環(huán)
// for(int i=0;i<numbers.length;i++){
// for(int j = numbers.length-1;j>i;j--){
// if (numbers[i]+numbers[j]==target){
// a[0] = i+1;
// a[1] = j+1;
// }else if(numbers[i]+numbers[j]<target){
// break;
// }
// }
// }
return a;
}
}
題目：給定一個字符串，驗證它是否是回文串，只考慮字母和數(shù)字字符项棠，可以忽略字母的大小寫悲雳。空字符串定義為有效的回文串沾乘。
示例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
算法思路：使用語言中的字符串翻轉(zhuǎn) API 得到 sgood 的逆序字符串 sgood_rev怜奖，只要這兩個字符串相同浑测，那么 sgood\textit{sgood}sgood 就是回文串翅阵。
class Solution {
public boolean isPalindrome(String s) {
StringBuffer sgood = new StringBuffer();
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isLetterOrDigit(ch)) {
sgood.append(Character.toLowerCase(ch));
}
}
StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
return sgood.toString().equals(sgood_rev.toString());
}
}
使用雙指針。初始時迁央，左右指針分別指向 sgood 的兩側(cè)掷匠，隨后我們不斷地將這兩個指針相向移動，每次移動一步岖圈，判斷這兩個指針指向的字符是否相同讹语。遇到其他字符前進(jìn)一位，當(dāng)這兩個指針相遇時蜂科，就說明 sgood 是回文串顽决。
class Solution {
public boolean isPalindrome(String s) {
StringBuffer sgood = new StringBuffer();
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isLetterOrDigit(ch)) {
sgood.append(Character.toLowerCase(ch));
}
}
int n = sgood.length();
int left = 0, right = n - 1;
while (left < right) {
if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
return false;
}
++left;
--right;
}
return true;
}
}
思路同上，首尾設(shè)置兩個指針导匣，遇到其他字符前進(jìn)一位才菠，兩指針遇到不相同的字符，就返回false贡定，直到兩指針相遇跳出循環(huán)返回true赋访。judjeChar() 函數(shù)可用isLetterOrDigit() 代替，不用自己寫缓待。
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
// byte[] array = new byte[s.getBytes().length];
int i = 0,j = 0,m = 0;
if(s.length() > 0){
j = s.length() - 1;
m = (s.length())/2;
}else{
return true;
}
while(i<j){
if(!(judjeChar(s.charAt(i)))){
i++;
}
if(!(judjeChar(s.charAt(j)))){
j--;
}
System.out.println("i="+i+"值是"+s.charAt(i)+" "+"j="+j+"值是"+s.charAt(j));
if(judjeChar(s.charAt(i)) && judjeChar(s.charAt(j))){
if(!(s.charAt(i) == (int)s.charAt(j))){
return false;
}
i++;
j--;
}
}
return true;
}
public boolean judjeChar(char ch){
// 判斷字符是否是英文或數(shù)字蚓耽，不是反回 false 否則反回 true
int num = (int) ch;
if(num <= 122 && num >= 97){
return true;
}else if(num >= 48 && num <= 57){
return true;
}else {
return false;
}
}
}
題目：編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來旋炒。輸入字符串以字符數(shù)組 char[] 的形式給出步悠。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組瘫镇、使用 O(1) 的額外空間解決這一問題鼎兽。你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。
算法思想：設(shè)置左右兩個指針汇四，分別交換兩指針?biāo)赶虻闹到幽危傧蚯耙苿印?/strong>
public void reverseString(char[] s) {
char one;
int i = 0;
int j = 0;
if(s.length > 0){
j = s.length - 1;
}
while(i<j){
one = s[i];
s[i] = s[j];
s[j] = one;
i++;
j--;
}
}
題目：編寫一個函數(shù)，以字符串作為輸入通孽，反轉(zhuǎn)該字符串中的元音字母序宦。
示例 1：
輸入："hello"
輸出："holle"
算法思想：設(shè)置左右兩個指針，判斷不是元音字母背苦，則向前進(jìn)一位互捌，直至兩指針均指向元音字母潘明，交換兩指針的值。重復(fù)上述過程秕噪，至兩指針相遇钳降。
class Solution {
public String reverseVowels(String s) {
char[] str = s.toCharArray();
for(int i = 0;i<str.length;i++){
System.out.println(str[i]);
}
char ch;
int i=0,j=0;
if(s.length()>0){
j = s.length() - 1;
}else{
return "";
}
while(i<j){
if(!yuanyin(s.charAt(i))){
i++;
}
if(!yuanyin(s.charAt(j))){
j--;
}
if(yuanyin(s.charAt(i)) && yuanyin(s.charAt(j))){
ch = str[i];
str[i] = str[j];
str[j] = ch;
i++;
j--;
}
}
return new String(str);
}
public boolean yuanyin(char c){
if (c == 'a' || c == 'e' || c == 'i'|| c == 'o'|| c == 'u'||c == 'A' || c == 'E' || c == 'I'|| c == 'O'|| c == 'U'){
return true;
}else{
return false;
}
}
}
題目：給你 n 個非負(fù)整數(shù) a1，a2腌巾，...遂填，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 澈蝙。在坐標(biāo)內(nèi)畫 n 條垂直線吓坚，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線灯荧，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水礁击。
說明：你不能傾斜容器，且 n 的值至少為 2逗载。
算法思想：設(shè)置左右兩個指針從數(shù)組兩端開始遍歷哆窿，先算出當(dāng)前最大面積。再比較兩指針指向的值厉斟，較小的一方挚躯，前進(jìn)一位，再算出當(dāng)前最大面積
方法二：雙重循環(huán)捏膨，暴力破解秧均。
public int maxArea(int[] height) {
int left = 0,right = height.length - 1;
int maxArea = 0;
while(left<right){
maxArea = Math.max(Math.min(height[left],height[right]) * (right - left) , maxArea);
if(height[left] <= height[right]){
left ++;
}else if(height[left] > height[right]){
right --;
}
}
return maxArea;
}
五、滑動窗口——雙索引
- 長度最小的子數(shù)組 (209)——facebook面試題
題目：給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s 号涯，找出該數(shù)組中滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組目胡，并返回其長度。如果不存在符合條件的子數(shù)組链快，返回 0誉己。
示例：
輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。
算法思想：滑動窗口域蜗。如果從i到j(luò)的和sum<s巨双，j++；擴(kuò)大窗口范圍霉祸，直到sum>s筑累；再讓i++；嘗試縮小窗口范圍丝蹭，找到最小的length慢宗。直到j(luò)>nums.length結(jié)束。
方法二：暴力解法，遍歷所有連續(xù)子數(shù)組镜沽，計算其和sum敏晤，驗證sum>=s是否成立。O(n^3)
方法三：優(yōu)化暴力解法：O(n^2)【不用每次都算sum缅茉，找到快速判斷的方法】
- 什么叫子數(shù)組嘴脾？連續(xù)子數(shù)組？
nums = [2,3,1,2,4,3]
子數(shù)組 num1=[1,3]
連續(xù)子數(shù)組 num2=[1,2,4]
public int minSubArrayLen(int s, int[] nums) {
int i = 0,j = 0;
int sumLength = 0;
int minSumLength = 0;
boolean first = true;
if(nums.length == 0){
return 0;
}
while(j <= nums.length){
int nowSum = 0;
for(int a =i;a<=j;a++){
nowSum = nowSum + nums[a];
}
if(j == nums.length-1 && nowSum < s){
return minSumLength;
}
if(nowSum < s){
j++;
}
if(nowSum >= s){
sumLength = j-i+1;
if(first){
first = false;
minSumLength = sumLength;
}else{
minSumLength = Math.min(sumLength,minSumLength);
}
i++;
}
}
return minSumLength;
}
- 官方答案蔬墩，思路一樣译打，代碼更簡練，時間更快筹我。（兩個while）
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
// 如果沒有ans（ans = 初始值Integer.MAX_VALUE）扶平，返回0帆离，否則返回ans蔬蕊。
return ans == Integer.MAX_VALUE ? 0 : ans;
}
(438)——要plus
最小覆蓋子串 (76)——太難了，直接看解析吧哥谷。
題目：給你一個字符串 S岸夯、一個字符串 T 。請你設(shè)計一種算法们妥，可以在 O(n) 的時間復(fù)雜度內(nèi)猜扮，從字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
輸入：S = "ADOBECODEBANC", T = "ABC"
輸出："BANC"
提示：
如果 S 中不存這樣的子串监婶，則返回空字符串 ""旅赢。
如果 S 中存在這樣的子串，我們保證它是唯一的答案惑惶。
算法思想：滑動窗口煮盼，如何判斷子字符串是否包含字符串T是關(guān)鍵。**
