求助：单循环下无重复索引的目标和子数组查找优化

• 需求：查找与给定目标值（checkval）匹配的数组子数组，需满足以下约束：仅允许使用单循环、求和时不可重复使用同一索引、禁止使用内置方法。
• 测试数组：int arr[] = { 2, 2, 1, 4, 1, 6, 8, 5, 1, 2, 1, 1, 1 };，目标值checkval=3。
• 现有代码存在两个问题：
  1. 重复打印单索引子数组（如多次输出index 3）；
  2. 子数组索引重复使用（例如找到index 8 to 10的子数组后，下一个子数组应从11开始而非9）。

现有代码 #

public class Main {

    public static void main(String[] args) {

        int arr[] = { 2, 2, 1, 4, 1, 6, 8, 5, 1, 2, 1, 1, 1 };
        int sum = 0;
        int indexval = 0;
        int checkval = 4;
        int i = 0;

        int len[] = new int[10];
        int l = 0;
        int lm = 0;

        System.out.println("the subarrays are: ");

        while (indexval <= arr.length) {
            int temp=i;

            if (i < arr.length)
                sum += arr[i];
            else
                break;

            if (sum <= checkval) {
                if (sum == checkval) {
                    System.out.println("index " + indexval + " to " + i);
                    len[l++] = i - indexval + 1;
                    lm = (i - indexval + 1) > len[l] ? (i - indexval + 1) : len[l];
                    i = indexval;
                    indexval += 1;
                    sum = 0;
                }
            }

            else if (arr[temp] == checkval) {
                System.out.println("index " + i);
                i = indexval;
                indexval += 1;
                sum = 0;
            }

            else if (sum > checkval) {
                i = indexval;
                indexval += 1;
                sum = 0;
            }

            i += 1;
        }
        
        System.out.println("Subarray with most elements is " + lm);

    }

}

优化后的代码 #

public class Main {
    public static void main(String[] args) {
        int arr[] = { 2, 2, 1, 4, 1, 6, 8, 5, 1, 2, 1, 1, 1 };
        int checkval = 3;
        int sum = 0;
        int start = 0;
        int maxLength = 0;

        System.out.println("the subarrays are: ");

        // 单循环遍历，end作为唯一迭代变量
        for (int end = 0; end < arr.length; end++) {
            sum += arr[end];

            // 当和超过目标值时，移动start指针缩小窗口，直到sum<=checkval
            while (sum > checkval) {
                sum -= arr[start];
                start++;
            }

            // 找到匹配目标值的子数组
            if (sum == checkval) {
                int currentLength = end - start + 1;
                // 根据start和end是否相同，打印单索引或范围索引
                if (start == end) {
                    System.out.println("index " + start);
                } else {
                    System.out.println("index " + start + " to " + end);
                }

                // 更新最长子数组长度
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                }

                // 移动start指针，避免重复使用之前的索引，开启下一轮查找
                sum -= arr[start];
                start++;
            }
        }

        System.out.println("Subarray with most elements is " + maxLength);
    }
}

优化说明 #

• 采用滑动窗口思想，用start和end指针维护当前子数组范围，以end作为唯一循环迭代变量，满足单循环要求。
• 解决索引重复使用问题：找到匹配子数组后，主动移动start指针并从sum中减去对应元素值，确保下一次查找从start+1开始，彻底避免重复使用已处理的索引。
• 修复重复打印问题：移除原有代码中错误的单元素判断分支，统一通过start == end判断是否为单索引子数组，避免重复触发打印逻辑。
• 求和过程严格控制在start到end的范围内，不会重复累加同一元素，符合约束要求。
• 简化最长子数组长度计算逻辑，直接在匹配时更新maxLength，去掉原有代码中冗余的数组存储操作。

内容的提问来源于stack exchange，提问作者Sathish Kumar