Почему алгоритм 3 сумм смотрит только на подмассивы, которые находятся справа от определенного числа?

Question

Я смотрю на код, который решает проблему 3sum, основываясь на решении 2sum. Почему низкий должен быть int lo = index+1? Означает ли это, что когда мы смотрим на подмассивы, нас интересует только сумма чисел справа от цели? Как насчет чисел слева от цели?

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 2) {
            return new ArrayList<>();
        }

        List<List<Integer>> results = new ArrayList<>();
        Arrays.sort(nums);

        for (int i=0; i<nums.length; i++) {
            if (i != 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            results.addAll(twoSum(nums, i));
        }
        return results;
    }

    private List<List<Integer>> twoSum(int[] nums, int index) {
        List<List<Integer>> results = new ArrayList<>();

        int target = -nums[index];
        int lo = index+1, hi = nums.length-1;
        while (lo < hi) {
            if (target == nums[lo] + nums[hi]) {
                List<Integer> result = Arrays.asList(nums[lo], nums[hi], -target);
                results.add(result);
                lo++;
                hi--;

                while (lo < hi && nums[lo] == nums[lo - 1])
                    lo++;  // skip same result
                while (lo < hi && nums[hi] == nums[hi + 1])
                    hi--;  // skip same result
            } else if (target < nums[lo] + nums[hi]) {
                hi--;
            } else {
                lo++;
            }
        }
        return results;
    }
}

Answer 1

Поскольку для каждого числа num[i] в позиции i, вы можете использовать алгоритм 2-суммы в массиве [i+1...N], чтобы найти два числа так, чтобы их сумма равнялась -num[i], что означает сумму 3число равно 0.

Например,

Пусть массив будет [-1, 0, 1, 2, -1, -4]

Алгоритм найдет любые 2-суммы в [0, 1, 2, -1, -4], равные 1

Тогда он найдет любые 2-суммы в [1, 2, -1, -4], равные 0

и т. Д.

Теперь вы можете увидеть начальную точку подмассива:i+1 при поиске 2-суммы для num[i], поэтому int lo = index + 1

Поиск исчерпывающий, поэтому будут найдены все кортежи, сумма которых равна 0.