1承冰、兩數(shù)之和 || ->167.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

• 題目描述：在有序數(shù)組中找出兩個(gè)數(shù)，使它們的和為 target
• 題解：使用雙指針咬荷，一個(gè)指針指向值較小的元素路呜，一個(gè)指針指向值較大的元素迷捧。指向較小元素的指針從頭向尾遍歷，指向較大元素的指針從尾向頭遍歷胀葱。
  • 如果兩個(gè)指針指向元素的和 sum == target漠秋，那么得到要求的結(jié)果；
  • 如果 sum > target抵屿，移動(dòng)較大的元素庆锦，使 sum 變小一些；
  • 如果 sum < target轧葛，移動(dòng)較小的元素搂抒，使 sum 變大一些。
  • 數(shù)組中的元素最多遍歷一次尿扯，時(shí)間復(fù)雜度為 O(N)求晶。只使用了兩個(gè)額外變量，空間復(fù)雜度為 O(1)衷笋。

public int[] twoSum(int[] numbers, int target) {
        int i=0,j=numbers.length-1;
        while(i<j){
            int sum=numbers[i]+numbers[j];
            if(sum==target){
                return new int[]{i+1,j+1};
            }else if(sum<target){
                i++;
            }else{
                j--;
            }
        }
        return null;
    }

2誉帅、平方數(shù)之和->633.

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

• 題目描述：判斷一個(gè)非負(fù)整數(shù)是否為兩個(gè)整數(shù)的平方和。
• 題解：可以看成是在元素為 0~target 的有序數(shù)組中查找兩個(gè)數(shù)右莱，使得這兩個(gè)數(shù)的平方和為 target蚜锨，如果能找到，則返回 true慢蜓，表示 target 是兩個(gè)整數(shù)的平方和亚再。
  • 本題和上面那道題類(lèi)似，只有一個(gè)明顯區(qū)別：一個(gè)是和為 target晨抡，一個(gè)是平方和為 target氛悬。本題同樣可以使用雙指針得到兩個(gè)數(shù)则剃，使其平方和為 target。
  • 本題的關(guān)鍵是右指針的初始化如捅，實(shí)現(xiàn)剪枝棍现，從而降低時(shí)間復(fù)雜度。設(shè)右指針為 x镜遣，左指針固定為 0己肮，為了使 02 + x2 的值盡可能接近 target，我們可以將 x 取為 sqrt(target)悲关。
  • 復(fù)雜度分析：因?yàn)樽疃嘀恍枰闅v一次 0~sqrt(target)谎僻，所以時(shí)間復(fù)雜度為 O(sqrt(target))。又因?yàn)橹皇褂昧藘蓚€(gè)額外的變量寓辱，因此空間復(fù)雜度為 O(1)艘绍。

 public boolean judgeSquareSum(int c) {
        int i=0,j=(int)Math.sqrt((double)c);

        while(i<=j){
            if((i*i+j*j)==c){
                return true;
            }else if((i*i+j*j)>c){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }

3、反轉(zhuǎn)字符串中的元音字符->345.

Given s = "leetcode", return "leotcede".

• 題解：使用雙指針秫筏，一個(gè)指針從頭向尾遍歷诱鞠，一個(gè)指針從尾到頭遍歷，當(dāng)兩個(gè)指針都遍歷到元音字符時(shí)这敬，交換這兩個(gè)元音字符航夺。為了快速判斷一個(gè)字符是不是元音字符，我們將全部元音字符添加到集合 HashSet 中鹅颊，從而以 O(1) 的時(shí)間復(fù)雜度進(jìn)行該操作。
  • 時(shí)間復(fù)雜度為 O(N)：只需要遍歷所有元素一次
  • 空間復(fù)雜度 O(1)：只需要使用兩個(gè)額外變量
  • 注意：這里并不是位置對(duì)應(yīng)的墓造，如果是位置對(duì)應(yīng)的可以使用兩個(gè)StringBuilder來(lái)分別接收從小到大堪伍，和從大到小的兩個(gè)字符串，最后反轉(zhuǎn)一下拼接觅闽。

 private static final HashSet<Character> vowel=new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
    public String reverseVowels(String s) {
        int i=0,j=s.length()-1;
        char[] result=new char[s.length()];
        while(i<=j){
            char ci=s.charAt(i);
            char cj=s.charAt(j);
            if(!vowel.contains(ci)){
                result[i++]=ci;
            }else if(!vowel.contains(cj)){
                result[j--]=cj;
            }else{
                result[i++]=cj;
                result[j--]=ci;
            }
    }
     return new String(result);
    }

4帝雇、回文字符串->680

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

• 題目描述：可以刪除一個(gè)字符，判斷是否能構(gòu)成回文字符串蛉拙。
• 所謂的回文字符串尸闸，是指具有左右對(duì)稱(chēng)特點(diǎn)的字符串，例如 "abcba" 就是一個(gè)回文字符串孕锄。
• 題解
  • 本題的關(guān)鍵是處理刪除一個(gè)字符吮廉。在使用雙指針遍歷字符串時(shí)，如果出現(xiàn)兩個(gè)指針指向的字符不相等的情況畸肆，我們就試著刪除一個(gè)字符宦芦，再判斷刪除完之后的字符串是否是回文字符串。
  • 注意：在出現(xiàn)不相等的時(shí)候不能簡(jiǎn)簡(jiǎn)單單的判斷一下是否和下一個(gè)相等就可以了轴脐，還要判斷后面全部的是不是相等调卑，因此這里使用函數(shù)的調(diào)用比較好抡砂。

public boolean validPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
        }
    }
    return true;
}

private boolean isPalindrome(String s, int i, int j) {
    while (i < j) {
        if (s.charAt(i++) != s.charAt(j--)) {
            return false;
        }
    }
    return true;
}

5、歸并兩個(gè)有序數(shù)組->88

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

• 題目描述：把歸并結(jié)果存到第一個(gè)數(shù)組上恬涧。注益。
• 題解
  • 需要從尾開(kāi)始遍歷，否則在 nums1 上歸并得到的值會(huì)覆蓋還未進(jìn)行歸并比較的值溯捆。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int index1 = m - 1, index2 = n - 1;
    int indexMerge = m + n - 1;
    while (index1 >= 0 || index2 >= 0) {
        if (index1 < 0) {
            nums1[indexMerge--] = nums2[index2--];
        } else if (index2 < 0) {
            nums1[indexMerge--] = nums1[index1--];
        } else if (nums1[index1] > nums2[index2]) {
            nums1[indexMerge--] = nums1[index1--];
        } else {
            nums1[indexMerge--] = nums2[index2--];
        }
    }
}

6丑搔、判斷鏈表是否存在環(huán)->141

• 題解
  • 使用雙指針，一個(gè)指針每次移動(dòng)一個(gè)節(jié)點(diǎn)现使，一個(gè)指針每次移動(dòng)兩個(gè)節(jié)點(diǎn)低匙，如果存在環(huán)，那么這兩個(gè)指針一定會(huì)相遇

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode l1 = head, l2 = head.next;
    while (l1 != null && l2 != null && l2.next != null) {
        if (l1 == l2) {
            return true;
        }
        l1 = l1.next;
        l2 = l2.next.next;
    }
    return false;
}