时间戳

首页 > 解决方案 > 我该如何解决这个问题，如果有的话，什么样的算法适合解决它

java - 我该如何解决这个问题，如果有的话，什么样的算法适合解决它

问题描述

有一个包含非负整数的数组。我需要找到一个包含总和等于给定数字（目标）的数字的子数组（如果有的话）。我编写了这个有效的代码，但我尝试以更有效的方式编写它（O（n））。

public static void solvedNotSoEnhanced(int[] arr, int target) {
    for (int i = 0; i <= arr.length-1;i++) {
        int cur_sum = 0;
        for (int j = i ; j <= arr.length-1; j++) {
            cur_sum += arr[j];
            if (cur_sum > target) {
                break;
            } else if (cur_sum == target) {
                System.out.println("start: " + i + " end: " + j);
            }
        }
    }
}

标签： javaalgorithm

解决方案

诀窍在于限制：

有一个包含非负整数的数组。

这意味着当您从前到后遍历输入时，您假定子数组的“开始”位于索引 0 处，然后您开始按顺序添加每个数字。由于该限制，只有 3 个选项：

  1. 添加新数字会导致总和小于所需数字。在这种情况下，继续前进。
  2. 添加新号码会导致与所需号码完全匹配。您已经找到了子序列并且算法完成了。
  3. 添加新数字会导致总和更多。在这种情况下，唯一的答案可能在于移动启动：元素 0不是解决方案的一部分。

因此：

static void solvedNotSoEnhanced(int[] arr, int target) {
    if (target < 1) {
        // Always mind your corner cases!
        System.out.println("(0, 0)");
        return;
    }

    int start = 0;
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];

        while (sum > target) {
            // Target exceeded; move up our startpoint.
            sum -= arr[start];
            start++;
        }

        // If we get here, we found our subsequence!
        if (sum == target) {
            System.out.println("[" + start + ", " + i + "]");
            return;
        }
    }
    return "No subsequence";
}

推荐阅读