• 数组累加和问题

    目录

    一、累加和等于num的最长子数组的长度（无负数）

    二、累加和等于num的最长子数组的长度（有负数）

    三、累加和小于等于num的最长子数组的长度

    一、累加和等于num的最长子数组的长度（无负数）

    问题：

            给定一个数组arr， 全是正数； 一个整数K， 求累加和等于K的， 最长子数组。

    思路：

            以使用双指针，一个在左L，一个在右R，形成一个窗口区域。当窗口中的值小于K时，窗口右边界扩大。当窗口中的值大于或等于K时，由于数组中全为正数，所以窗口右边界再扩大，窗口中的值会大于K。所以此时需要窗口左边界右移。当窗口右边界扩大到某个元素，且窗口中的值等于K，计算窗口中此时的长度，与原本系统中的长度作比较，取最大值进行保存。当窗口右边界到达数组最后一个元素，且窗口中的值小于K，直接返回，不做任何操作。最后返回系统中保存得最大长度。

    代码：

    1. public class LongestSumSubArrayLengthInPositiveArray {
    2.  
    3. 	public static int getMaxLength(int[] arr, int K) {
    4. 		if (arr == null || arr.length == 0 || K <= 0) {
    5. 			return 0;
    6. 		}
    7. 		//[L,R]
    8. 		int L = 0;
    9. 		int R = 0;
    10. 		int wsum = arr[0];
    11. 		int len = 0;
    12. 		while (R < arr.length) {
    13. 			if (wsum == K) {
    14. 				len = Math.max(len, R - L + 1);
    15. 				wsum -= arr[L++];
    16. 			} else if (wsum < K) {
    17. 				R++;
    18. 				if (R == arr.length) {
    19. 					break;
    20. 				}
    21. 				wsum += arr[R];
    22. 			} else {
    23. 				wsum -= arr[L++];
    24. 			}
    25. 		}
    26. 		return len;
    27. 	}
    28.  
    29. 	// for test
    30. 	public static int right(int[] arr, int K) {
    31. 		int max = 0;
    32. 		for (int i = 0; i < arr.length; i++) {
    33. 			for (int j = i; j < arr.length; j++) {
    34. 				if (valid(arr, i, j, K)) {
    35. 					max = Math.max(max, j - i + 1);
    36. 				}
    37. 			}
    38. 		}
    39. 		return max;
    40. 	}
    41.  
    42. 	// for test
    43. 	public static boolean valid(int[] arr, int L, int R, int K) {
    44. 		int sum = 0;
    45. 		for (int i = L; i <= R; i++) {
    46. 			sum += arr[i];
    47. 		}
    48. 		return sum == K;
    49. 	}
    50.  
    51. 	// for test
    52. 	public static int[] generatePositiveArray(int size, int value) {
    53. 		int[] ans = new int[size];
    54. 		for (int i = 0; i != size; i++) {
    55. 			ans[i] = (int) (Math.random() * value) + 1;
    56. 		}
    57. 		return ans;
    58. 	}
    59.  
    60. 	// for test
    61. 	public static void printArray(int[] arr) {
    62. 		for (int i = 0; i != arr.length; i++) {
    63. 			System.out.print(arr[i] + " ");
    64. 		}
    65. 		System.out.println();
    66. 	}
    67.  
    68. 	public static void main(String[] args) {
    69. 		int len = 50;
    70. 		int value = 100;
    71. 		int testTime = 500000;
    72. 		System.out.println("test begin");
    73. 		for (int i = 0; i < testTime; i++) {
    74. 			int[] arr = generatePositiveArray(len, value);
    75. 			int K = (int) (Math.random() * value) + 1;
    76. 			int ans1 = getMaxLength(arr, K);
    77. 			int ans2 = right(arr, K);
    78. 			if (ans1 != ans2) {
    79. 				System.out.println("Oops!");
    80. 				printArray(arr);
    81. 				System.out.println("K : " + K);
    82. 				System.out.println(ans1);
    83. 				System.out.println(ans2);
    84. 				break;
    85. 			}
    86. 		}
    87. 		System.out.println("test end");
    88. 	}
    89.  
    90. }

    二、累加和等于num的最长子数组的长度（有负数）

    问题：

            给定一个数组arr， 一个整数（存在负数）K， 求累加和等于K的， 最长子数组。

    代码：

    1. public class LongestSumSubArrayLength {
    2.  
    3. 	public static int maxLength(int[] arr, int k) {
    4. 		if (arr == null || arr.length == 0) {
    5. 			return 0;
    6. 		}
    7. 		// key:前缀和
    8. 		// value : 0~value这个前缀和是最早出现key这个值的
    9. 		HashMap map = new HashMap();
    10. 		map.put(0, -1); // important
    11. 		int len = 0;
    12. 		int sum = 0;
    13. 		for (int i = 0; i < arr.length; i++) {
    14. 			sum += arr[i];
    15. 			if (map.containsKey(sum - k)) {
    16. 				len = Math.max(i - map.get(sum - k), len);
    17. 			}
    18. 			if (!map.containsKey(sum)) {
    19. 				map.put(sum, i);
    20. 			}
    21. 		}
    22. 		return len;
    23. 	}
    24.  
    25. 	// for test
    26. 	public static int right(int[] arr, int K) {
    27. 		int max = 0;
    28. 		for (int i = 0; i < arr.length; i++) {
    29. 			for (int j = i; j < arr.length; j++) {
    30. 				if (valid(arr, i, j, K)) {
    31. 					max = Math.max(max, j - i + 1);
    32. 				}
    33. 			}
    34. 		}
    35. 		return max;
    36. 	}
    37.  
    38. 	// for test
    39. 	public static boolean valid(int[] arr, int L, int R, int K) {
    40. 		int sum = 0;
    41. 		for (int i = L; i <= R; i++) {
    42. 			sum += arr[i];
    43. 		}
    44. 		return sum == K;
    45. 	}
    46.  
    47. 	// for test
    48. 	public static int[] generateRandomArray(int size, int value) {
    49. 		int[] ans = new int[(int) (Math.random() * size) + 1];
    50. 		for (int i = 0; i < ans.length; i++) {
    51. 			ans[i] = (int) (Math.random() * value) - (int) (Math.random() * value);
    52. 		}
    53. 		return ans;
    54. 	}
    55.  
    56. 	// for test
    57. 	public static void printArray(int[] arr) {
    58. 		for (int i = 0; i != arr.length; i++) {
    59. 			System.out.print(arr[i] + " ");
    60. 		}
    61. 		System.out.println();
    62. 	}
    63.  
    64. 	public static void main(String[] args) {
    65. 		int len = 50;
    66. 		int value = 100;
    67. 		int testTime = 500000;
    68.  
    69. 		System.out.println("test begin");
    70. 		for (int i = 0; i < testTime; i++) {
    71. 			int[] arr = generateRandomArray(len, value);
    72. 			int K = (int) (Math.random() * value) - (int) (Math.random() * value);
    73. 			int ans1 = maxLength(arr, K);
    74. 			int ans2 = right(arr, K);
    75. 			if (ans1 != ans2) {
    76. 				System.out.println("Oops!");
    77. 				printArray(arr);
    78. 				System.out.println("K : " + K);
    79. 				System.out.println(ans1);
    80. 				System.out.println(ans2);
    81. 				break;
    82. 			}
    83. 		}
    84. 		System.out.println("test end");
    85.  
    86. 	}
    87.  
    88. }

    三、累加和小于等于num的最长子数组的长度

    题目：

            给定一个数组arr， 值可正， 可负， 可0； 一个整数aim， 求累加和小于等于aim的， 最长子数组， 要求时间复杂度O(N)

    思路：

            设计两个数组minSums和minSumEnds，长度为给定数组的长度。数组元素minSums[i]表示以arr[i]开头，累加和最小的最长子数组的累加和；数组元素minSumEnds[i]与数组元素minSums[i]相对应，表示以arr[i]开头，累加和最小的最长子数组的右边界下标。

            通过反向遍历数组，得到数组minSums和minSumEnds。

    代码：

    1. public class LongestLessSumSubArrayLength {
    2.  
    3. 	public static int maxLengthAwesome(int[] arr, int k) {
    4. 		if (arr == null || arr.length == 0) {
    5. 			return 0;
    6. 		}
    7. 		
    8. 		int N = arr.length;
    9. 		int[] minSums = new int[N];
    10. 		int[] minSumEnds = new int[N];
    11. 		
    12. 		minSums[N - 1] = arr[N - 1];
    13. 		minSumEnds[N - 1] = N - 1;
    14. 		
    15. 		for (int i = N - 2; i >= 0; i--) {
    16. 			if (minSums[i + 1] <= 0) {
    17. 				minSums[i] = arr[i] + minSums[i + 1];
    18. 				minSumEnds[i] = minSumEnds[i + 1];
    19. 			} else {
    20. 				minSums[i] = arr[i];
    21. 				minSumEnds[i] = i;
    22. 			}
    23. 		}
    24. 		
    25. 		
    26. 		// 迟迟扩不进来那一块儿的开头位置
    27. 		//(i...)(...)(...)(end..X)	end这一块扩不进来了
    28. 		int end = 0;
    29. 		//i.......(sum)  end
    30. 		int sum = 0;
    31. 		int len = 0;
    32. 		for (int i = 0; i < N; i++) {
    33. 			// while循环结束之后：
    34. 			// 1) 如果以i开头的情况下，累加和<=k的最长子数组是arr[i..end-1]，看看这个子数组长度能不能更新res；
    35. 			// 2) 如果以i开头的情况下，累加和<=k的最长子数组比arr[i..end-1]短，更新还是不更新res都不会影响最终结果；
    36. 			while (end < N && sum + minSums[end] <= k) {
    37. 				sum += minSums[end];
    38. 				end = minSumEnds[end] + 1;
    39. 			}
    40. 			len = Math.max(len, end - i);
    41. 			
    42. 			if (end > i) { // 还有窗口，哪怕窗口没有数字 [i~end) [4,4)
    43. 				sum -= arr[i];
    44. 			} else { // i == end,  即将 i++, i > end, 此时窗口概念维持不住了，所以end跟着i一起走
    45. 				end = i + 1;
    46. 			}
    47. 		}
    48. 		return len;
    49. 	}
    50.  
    51. 	public static int maxLength(int[] arr, int k) {
    52. 		int[] h = new int[arr.length + 1];
    53. 		int sum = 0;
    54. 		h[0] = sum;
    55. 		for (int i = 0; i != arr.length; i++) {
    56. 			sum += arr[i];
    57. 			h[i + 1] = Math.max(sum, h[i]);
    58. 		}
    59. 		sum = 0;
    60. 		int res = 0;
    61. 		int pre = 0;
    62. 		int len = 0;
    63. 		for (int i = 0; i != arr.length; i++) {
    64. 			sum += arr[i];
    65. 			pre = getLessIndex(h, sum - k);
    66. 			len = pre == -1 ? 0 : i - pre + 1;
    67. 			res = Math.max(res, len);
    68. 		}
    69. 		return res;
    70. 	}
    71.  
    72. 	public static int getLessIndex(int[] arr, int num) {
    73. 		int low = 0;
    74. 		int high = arr.length - 1;
    75. 		int mid = 0;
    76. 		int res = -1;
    77. 		while (low <= high) {
    78. 			mid = (low + high) / 2;
    79. 			if (arr[mid] >= num) {
    80. 				res = mid;
    81. 				high = mid - 1;
    82. 			} else {
    83. 				low = mid + 1;
    84. 			}
    85. 		}
    86. 		return res;
    87. 	}
    88.  
    89. 	// for test
    90. 	public static int[] generateRandomArray(int len, int maxValue) {
    91. 		int[] res = new int[len];
    92. 		for (int i = 0; i != res.length; i++) {
    93. 			res[i] = (int) (Math.random() * maxValue) - (maxValue / 3);
    94. 		}
    95. 		return res;
    96. 	}
    97.  
    98. 	public static void main(String[] args) {
    99. 		System.out.println("test begin");
    100. 		for (int i = 0; i < 10000000; i++) {
    101. 			int[] arr = generateRandomArray(10, 20);
    102. 			int k = (int) (Math.random() * 20) - 5;
    103. 			if (maxLengthAwesome(arr, k) != maxLength(arr, k)) {
    104. 				System.out.println("Oops!");
    105. 			}
    106. 		}
    107. 		System.out.println("test finish");
    108. 	}
    109.  
    110. }

    参考：累加和等于num的最长子数组的长度_GoSantiago的博客-CSDN博客

  • 相关阅读:
    材质、纹理、贴图的区别和关联
    新闻发稿多少钱一篇？轻松发布新闻一站式发稿服务平台
    探讨NLP对行业大量数据信息抽取的技术实现
    彻底搞懂kubernetes调度框架与插件
    Grafana离线安装部署以及插件安装
    泛型擦除的理解
    Linux下yum源配置实战 2
    基于SpringBoot的电影评论网站
    JavaScript -- 03. 运算符介绍
    是时候来点现代c++了 c++11之超级重要之smart pointer详细解析
  • 原文地址：https://blog.csdn.net/z1171127310/article/details/127430442