java 给定和的连续子阵

vq8itlhq  于 2023-04-04  发布在  Java
关注(0)|答案(1)|浏览(97)

我试图从一个给定的数组中创建一个连续的subArray,它等于给定的sum,并将第一个和最后一个索引作为ArrayList返回。这是我能想到的解决方案,实际上通过了52个测试用例,但在一个非常大的数组集合中失败了,它返回-1。Input - arr = {1,2,3,7,5} n = 5 s = 12Expected output = 2, 4

static ArrayList<Integer> subarraySum(int[] arr, int n, int s) {
    ArrayList<Integer> result = new ArrayList<>();
    result.add(0, -1);
    for (int i = 0; i < n; i++) {
        int sum = arr[i];
        for (int j = i+1; j < n; j++) {
            sum += arr[j];
            if (sum == s) {
                result.add(1, j+1);
                result.set(0, i+1);
                return result;
            }
        }
    }
    return result;
}
i2byvkas

i2byvkas1#

下面的代码应该有效:

static ArrayList<Integer> subarraySum(int[] arr, int s) {
    ArrayList<Integer> result = new ArrayList<>();
    
    for (int i = 0; i < arr.length; i++) {
        int sum = 0;
        for (int j = i; j < arr.length; j++) {
            sum += arr[j];
            
            if (s == sum) {
                result.add(i+1);
                result.add(j+1);
                return result;
            }
        }
    }
    
    result.add(-1);
    return result;
}

相关问题