LIXI.FUN

public class Solution {
    public boolean hasCycle(ListNode head) {

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // 快慢指针相遇则意味着有环
            if (slow == fast) {
                return true;
            }
        }

        // 跳出 while 则意味着没有环
        return false;
    }
}

class Solution {
    public int[] sortArray(int[] nums) {

        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        // 快速排序算法偏爱 随机
        // 随机选择一个在 lo, hi 范围内的下标跟 lo 的下标替换
        int rand = ThreadLocalRandom.current().nextInt(lo, hi);
        swap(nums, lo, rand);

        int i = lo;
        int j = hi;
        int pivot = nums[lo];

        while (i < j) {
            // 对于下面两行为什么不能调换位置
            // 什么情况下能调换位置
            // 拉到最下面去看 参考里的 [为什么经典快排先从右往左找]
            while (i < j && nums[j] >= pivot) j--;
            while (i < j && nums[i] <= pivot) i++;

            swap(nums, i, j);
        }

        swap(nums, lo, i);
        qsort(nums, lo, i - 1);
        qsort(nums, i + 1, hi);
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {

        int notZeroIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && i != ++notZeroIndex) {
                nums[notZeroIndex] = nums[i];
                nums[i] = 0;
            }
        }
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        int n = nums.length;

        // 有序之后才可以用左右指针来根据元素大小进行移动
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();

        int a, b, c;

        // 固定一个最小元素，再左右指针去找另外两个元素
        for (int i = 0; i < n - 2; i++) {
            // a 为最小元素，若最小元素大于 0 则和不可能为 0，跳出
            if ((a = nums[i]) > 0) break;

            // 跳过相同的元素
            if (i != 0 && nums[i] == nums[i - 1]) continue;

            // 左指针从 i + 1 开始，向右移动
            // 右指针从 n - 1 开始，向左移动
            for (int j = i + 1, k = n - 1; j < k;) {
                b = nums[j];
                c = nums[k];

                int sum = a + b + c;

                if (sum == 0) {
                    res.add(Arrays.asList(a, b, c));

                    // 跳过相同的元素，注意这里是 ++j 即为非相同元素下标
                    while (j < k && nums[j] == nums[++j]);
                    while (j < k && nums[k] == nums[--k]);
                } else if (sum < 0) {
                    // 和小于 0 需要一个更大的数字，左指针右移
                    ++j;
                } else {
                    // 和大于 0 需要一个更小的数字，右指针左移
                    --k;
                }
            }
        }

        return res;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {

        // 没有重复元素，可以构建 value 对应 index 的哈希表
        Map<Integer, Integer> valueToIndex = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int preNum = target - nums[i];
            if (valueToIndex.containsKey(preNum)) {
                return new int[] {valueToIndex.get(preNum), i};
            }
            valueToIndex.put(nums[i], i);
        }

        throw new RuntimeException();
    }
}