如何将 O(n^2) 复杂度降低到 O(n) ？

Question

给定一个大小为 N 且仅包含正整数的未排序数组 A，找到一个与给定数字 S 相加的连续子数组，并返回该子数组的左右索引（从 1 开始索引）。

如果有多个子数组，则返回从左向右移动时最先出现的子数组索引。

注意：- 您必须返回一个由左右两个元素组成的 ArrayList。如果不存在这样的子数组，则返回一个由元素 -1 组成的数组。

 static ArrayList<Integer> subarraySum(int[] arr, int n, int s) 
    {
        // Your code here
        for (int i =0 ; i < n; i++){
            int acc = 0;
            for ( int j =i;j < n; j++ ){
                acc += arr[j];
                if(acc == s){
                    return new ArrayList<>(Arrays.asList(i+1,j+1));
                }
                if(acc > s){
                    break;
                }
            }
        }
        return new ArrayList<>(Arrays.asList(-1));
    }

我有这段代码，任何人都可以帮助我降低其时间复杂度吗？

Answer 1

这应该可以帮助您开始。

 static ArrayList<Integer> subarraySum(int[] arr, int n, int s) {
        int start = 0;
        int end = 0;
        int currentSum = 0;

        while (end < n || currentSum > s) {
            if (currentSum == s) {
                return new ArrayList<>(Arrays.asList(start + 1, end));
            } else if (currentSum < s) {
                currentSum += arr[end];
                end++;
            } else {
                currentSum -= arr[start];
                start++;
            }
        }

        return new ArrayList<>(Arrays.asList(-1));
    }

Answer 2

这行得通吗？

static ArrayList<Integer> subarraySum(int[] arr, int n, int s) {
        int start = 0;
        int end = 0;
        int currentSum = 0;

        while (end < n || currentSum >= s) {
            if (currentSum == s) {
                return new ArrayList<>(Arrays.asList(start + 1, end));
            }
            if (currentSum < s) {
                if (end < n) {
                    currentSum += arr[end];
                    end++;
                } else {
                    break;
                }
            } else {
                currentSum -= arr[start];
                start++;
            }
        }
        return new ArrayList<>(Arrays.asList(-1));
    }