Leetcode #167 两数之和
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个有序数组，判断是否存在数组内的两个数相加等于目标值，双指针遍历数组，一个指针从最小值开始，另一指针从最大值开始。
左指针往右移动则使得和增加，右指针往左移则使得和减小

    public static int[] twoSum(int[] numbers, int target) {
        int l = 0;
        int r = numbers.length - 1;
        while(l < r){
            if(numbers[l] + numbers[r] == target){
                return new int[]{l+1,r+1};
            }else if(numbers[l] + numbers[r] > target){
                r--;
            }else if (numbers[l] + numbers[r] < target){
                l++;
            }
        }
        return null;
    }

Leetcode #15 三数之和
https://leetcode-cn.com/problems/3sum/
先把数组进行排序，从最左边元素开始定位，如果该元素大于0，则说明所有元素都大于0，不存在相加等于0的情况
然后从左边第二个元素和最末尾的元素开始相加，如果该3个元素相加等于0，则进入下一轮，如果大于0则说明需要一个更小的元素，右边的指针往左移，如果小于0则说明需要一个更大的元素，左边的指针往右移

public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return ans;
    }

Leetcode #19 删除链表的到数第n个节点
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
dummy头节点的作用是方便访问head链表，和处理链表只有一个元素的状况

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode nodeR = dummy;
        ListNode nodeL = dummy;
        for(int i = 1; i <= n+1; i++){
            nodeR = nodeR.next;
        }
        while(nodeR != null){
            nodeR = nodeR.next;
            nodeL = nodeL.next;
        }
        //此时nodeL的指针指向的是被删除节点的前一位，直接返回nodeL是错的
        nodeL.next = nodeL.next.next;
        return dummy.next;
    }

Leetcode #141 判断链表是否存在环
https://leetcode-cn.com/problems/linked-list-cycle
设定2个步长不一样的指针，如果链表中存在环，那么两个指针会相遇（一个指针追上另一个指针）。

public boolean hasCycle(ListNode head) {
         ListNode l1 = head;
         ListNode 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;
     }

Leetcode #345 反转字符串中元音字符
https://leetcode-cn.com/problems/linked-list-cycle
反转字符串中的元音字符（交换位置）
从字符串数组的两头开始往中间遍历，如果是元音，交换位置

public static String reverseVowels(String s) {
        int l = 0;
        int r = s.length() - 1;
        char[] sArr = s.toCharArray();
        while (l < r){
            if(!isVowel(sArr[l])){
                l++;
            }else if(!isVowel(sArr[r])){
                r--;
            }else if(isVowel(sArr[l]) && isVowel(sArr[r])){
                char temp = sArr[l];
                sArr[l] = sArr[r];
                sArr[r] = temp;
                l++;
                r--;
            }
        }
        return new String(sArr);
    }

private static boolean isVowel(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;
        }
        return false;
    }

Leetcode #88 合并两个有序数组
https://leetcode-cn.com/problems/merge-sorted-array
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。nums1的容量远大于nums2.

  /**
     * nums1 = [1,2,3,0,0,0], m = 3
     * nums2 = [2,5,6],       n = 3
     * 输出: [1,2,2,3,5,6]
     * 注意判断边界当 一个数组的有效元素取完时，只复制另一数组的元素
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int [] a = new int[m];
        System.arraycopy(nums1, 0, a, 0, m);
        int i = 0;
        int i1 = 0;
        int i2 = 0;
        while((i1 < m) || (i2 < n)){
            if(i1 != m && i2 != n && a[i1] < nums2[i2]){
                nums1[i] = a[i1];
                i1++;
            }else if(i1 != m && i2 != n && a[i1] > nums2[i2]){
                nums1[i] = nums2[i2];
                i2++;
            }else if(i1 == m){//当nums1的有效元素取完
                nums1[i] = nums2[i2];
                i2++;
            }else{//当nums2的有效元素取完
                nums1[i] = a[i1];
                i1++;
            }
            i++;
        }
    }

Leetcode #633 平方数之和
https://leetcode-cn.com/problems/sum-of-square-numbers
根两数和、三数和一样的解体思路，使用相对双指针。

    /* *
     * 判断对于常数c 是否存在两个整数n,m 使得n^2 + m^2 = c
     * 假设 m 为 c的开根号，那么如果对于所有大于m的整数都有其平方大于c
     * 所以整数必须在0-m之间选取，则令一个指针从0开始往右，令一指针从m开始往左移
     */
public static boolean judgeSquareSum(int c) {
        int result;
        int n = (int) Math.sqrt(c);
        int m = 0;
        while(m <= n){
            result = m*m + n*n;
            if(result > c){
                n--;
            }else if(result < c){
                m++;
            }else if(result == c){
                return true;
            }
        }
        return false;
    }

Leetcode #42 接雨水
https://leetcode-cn.com/problems/trapping-rain-water

    /**
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     *
     * 思路：两个指针，对于某一列的储水量，根据左右最短的高度决定
     * 所以从左到右遍历整个数组，求出每一个元素左边最高和右边最高就可以了
     *
     * 外部需要遍历n次，内部又要遍历n次 时间复杂度为O(n^2)
     */
public int trap(int[] height) {
        int result = 0;
        if(height == null || height.length == 0){
            return 0;
        }
        //最左和最右的柱子不可能储水
        for(int i = 1; i < height.length - 1; i++){
            int maxL = 0;
            int maxR = 0;
            for(int pL = i - 1; pL >= 0; pL--){
                maxL = Math.max(height[pL],maxL);
            }
            for(int pR = i + 1; pR < height.length; pR++){
                maxR = Math.max(height[pR],maxR);
            }
            if(Math.min(maxL,maxR) > height[i])
                result = result + Math.min(maxL,maxR) - height[i];
        }
        return result;
    }

    /**
     * 优化
     * 使用动态规划思想，第n根柱子的储水量决定与其左边最高柱子和右边最高柱子的最小值，
     * 创建2个数组，一个储存元素左边最高柱子的高度，另一个储存右边最高柱子的高度
     */
    public int trap1(int[] height) {
        int[] lMax = new int[height.length];
        int[] rMax = new int[height.length];
        int result = 0;

        for(int i = 0; i < height.length; i++){
            if(i == 0){
                lMax[i] = 0;
            }else {
                lMax[i] = Math.max(lMax[i-1],height[i-1]);
            }
        }
        for(int i = height.length - 1; i >= 0; i--){
            if(i == height.length - 1){
                rMax[i] = 0;
            }else {
                rMax[i] = Math.max(rMax[i+1],height[i+1]);
            }
        }
        for(int i = 1; i < height.length - 1; i++){
            //一定要判断当前柱子是否比左右都要高！！！
            if(Math.min(rMax[i],lMax[i]) > height[i])
                result = result + Math.min(rMax[i],lMax[i]) - height[i];
        }
        return result;
    }

Leetcode #3 无重复字符的最长子串
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

    /**
     *
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     *
     * 创建哈希表作为key-index的映射
     */
public static int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int result = 0;
        int i = 0;
        int j = 1;
        if(s.length() == 0 || s == null){
            return 0;
        }else if(s.length() == 1){
            return 1;
        }
        map.put(s.charAt(i),i);
        while(i < s.length() && j < s.length()){
            if(!map.containsKey(s.charAt(j))){
                map.put(s.charAt(j),j);
                result = Math.max(result,j-i+1);
            }else{
                i = Math.max(i,map.get(s.charAt(j))+1);
                map.put(s.charAt(j),j);
                result = Math.max(result,j-i+1);
            }
            j++;
        }
        return result;
    }

Leetcode #360 有序转化数组
https://leetcode-cn.com/problems/sort-transformed-array

    /**
     *
     * 给你一个已经 排好序 的整数数组 nums 和整数 a、b、c。对于数组中的每一个数 x，
     * 计算函数值 f(x) = ax2 + bx + c，请将函数值产生的数组返回。
     *
     * 要注意，返回的这个数组必须按照 升序排列，并且我们所期望的解法时间复杂度为 O(n)。
     *
     * 直接暴力API解决
     * 双指针考虑韦达定理求 极值点 和 对称线
     */
public static int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] result = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            result[i] = a*nums[i]*nums[i] + b*nums[i] + c;
        }
        Arrays.sort(result);
        return result;
    }

Leetcode #11 盛最多水的容器
https://leetcode-cn.com/problems/container-with-most-water/

question_11.jpg

    /**
     *
     * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
     * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     *
     * 思路：储水量又两块柱子的横坐标之差（j-1) 和 最短纵坐标 决定
     * area=（j-1)* min(height[i],height[j])
     * 两种移动方案，
     * 1.移动短板——面积可能增大可能减小，
     * 2.移动长板——面积一定减小
     * 每移动一次，横坐标之差（j-1)都会减少1，
     * 而面积由最短板决定，所以在横坐标之差减少时，如果移动长板，即最短板不变
     * 面积必然减小。所以只能移动长板
     */
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int area = 0;
        while(i < j){
            area = Math.max(area,Math.min(height[j],height[i]));
            if(height[i] < height[j]){
                i++;
            }else {
                j--;
            }
        }
        return area;
    }

Leetcode #524 通过删除匹配字符串
https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting

    /**
     * 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，
     * 该字符串可以通过删除给定字符串的某些字符来得到。
     * 如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
     *
     * 思路：先考虑一个字符串的情况，如果对于给定字符串先x，
     * 和字典字符串y，对于y中的每一个元素x都含有则说明
     * x可以经过删除得到y
     * 设定2个指针，一个指向x的头元素，一个指向y的头元素，
     * 如果相等则都往后移动一位，如果不相等则x的指针移动
     * 当y的指针移动到末尾时则说明元素全部可以匹配上
     */
public static String findLongestWord(String s, List<String> d) {
        String ans = "";
        for(String str : d){
            for(int i = 0, j = 0; i < s.length() && j < str.length(); i++){
                if(s.charAt(i) == str.charAt(j)){
                    j++;
                }
                if(j == str.length()){
                    if(ans.length() < str.length()
                            || (ans.length() == str.length() && ans.compareTo(str) > 0)){
                        ans = str;
                    }else if(ans.length() > str.length()
                            || (ans.length() == str.length() && ans.compareTo(str) <= 0)){
                        ans = ans;
                    }
                }
            }
        }
        return ans;
    }

Leetcode #680 验证是否为回文II
https://leetcode-cn.com/problems/valid-palindrome-ii
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

public static boolean validPalindrome(String s) {
        char[] sArr = s.toCharArray();
        int l = 0;
        int r = sArr.length - 1;
        while(l < r){
            if(sArr[l] != sArr[r]){ //不能用isPalindrome(sArr, l, r)判断，因为l,r没有自增或者自减
                return isPalindrome(sArr,l+1,r) || isPalindrome(sArr,l,r-1);
            }
            l++;
            r--;
        }
        return true;
    }

    private static boolean isPalindrome(char[] arr, int l, int r){
        while(l < r){
            if(arr[l] == arr[r]){
                l++;
                r--;
            }else {
                return false;
            }
        }
        return true;
    }