LeetCode之双指针法

双指针是一种思想或一种技巧并不是特别具体的算法。
具体就是用两个变量动态存储两个结点，来方便我们进行一些操作。通常用在线性的数据结构中。

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

题解：

class Solution {
   /**
     * 思路：
     * 设定：需要找到3个数，a+b+c=0, 这里 a b c三个数的下标从左到右
     * 定义a的下标为i，b的下标为left，c的下标为right
     * 首先，对数组进行排序
     * 则需要找nums[i]+nums[left]+nums[right] = 0，找到则放入集合中
     * 如果nums[i]+nums[left]+nums[right] > 0，则需right--
     * 如果nums[i]+nums[left]+nums[right] < 0，则需left++
     * 其次，a b c三个数都要去重
     * @param nums
     * @return
     */
    public List> threeSum(int[] nums) {
        List> list = new ArrayList<>();
        Arrays.sort(nums);  //排序
        int left = 0, right = 0;
        for (int i=0;i 0) {
                //当前最小数大于0，则找不到符合条件的组
                return list;
            }
            if (i>0 && nums[i] == nums[i-1]) {
                //对i去重:  如果当前组的a和上一组的a相等，则视为重复组
                continue;
            }
            left = i+1;
            right = nums.length-1;
            while(left 0) {
                    right--;
                } else if (temp < 0) {
                    left++;
                } else {
                    //找到符合条件组
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //将b c相同元素跳过，即去重
                    while(left < right && nums[left+1] == nums[left]) {
                        //将b去重
                        left++;
                    }
                    while(left < right && nums[right-1] == nums[right]) {
                        //将c去重
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return list;
    }

}

环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

题解：

public class Solution {

    public ListNode detectCycle(ListNode head) {
        //题解：这个题的目标，是找到环的入环点，
        // 根据上图，首先根据公式推导出  a = (n-1)(b+c) + c，通过这个公式，
        // 再用两个指针相同速度走，相遇点就是要返回的入环节点
        //那么第一步：定义一个快指针和慢指针，快指针每步走2个，慢指针每步走一个，在有环的情况下快指针一定会追上慢指针相遇
        //得到相交点，构成这幅图的形式

        ListNode slow = head, fast = head;
        while(fast != null) {
            //让慢指针每次走1步，快指针每次走2步
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (slow == fast) {
                //再构造两个慢指针走到入环节点
                ListNode cur = head;
                while(cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }
        return null;
    }
}

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

题解：

    4. 双单指针法
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums,i,p1);
                p1++;
            } else if (nums[i] == 0) {
               swap(nums,i,p0);
                if (p0 < p1) {
                    swap(nums,i,p1);
                }
                p0++;
                p1++;
            }
        }
    }

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

题解：

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //思路：双指针法
        // 创建数组nums3，遍历nums3，num1和nums2分别定义下标pos1,pos2，两个指针数元素比较大小，小的放入nums3中，相等的将num1的放入nums3中
        int p1 = 0, p2 = 0;
        int[] nums3 = new int[m+n]; //创建总长度m+n的数组存所有元素
        int cur; //当前应该插入的值
        while(p1

    public void moveZeroes(int[] nums) {
        //思路：双指针：指针i每遇到一个非0元素，就将慢指针j位置数设置为nums[i]，直到nums遍历完成
        //在j位置之后的元素都置为0，完成移动
        int j=0;
        for (int i=0;i