Advertisement
Guest User

grokking 234

a guest
Sep 21st, 2022
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.11 KB | None | 0 0
  1. class Solution {
  2.     public int minSumOfLengths(int[] nums, int target) {
  3.         Map<Integer, Integer> sums = new HashMap<>(); // prefix sum, index
  4.         sums.put(0, -1);
  5.        
  6.         int sum = 0; // prefix sum
  7.         for (int i = 0; i < nums.length; i++) {
  8.             sum += nums[i];
  9.             sums.put(sum, i);
  10.  
  11.             // store prefix sums to nums for the second loop
  12.             nums[i] = sum;
  13.         }
  14.        
  15.         int ans = Integer.MAX_VALUE;
  16.         int len1 = Integer.MAX_VALUE;
  17.         for (int i = 0; i < nums.length; i++) {
  18.             // Find minimum length of subarray ends at index <= i
  19.             if (sums.containsKey(nums[i] - target)) {
  20.                 len1 = Math.min(len1, i - sums.get(nums[i] - target));
  21.             }
  22.             // Find length of subarray starts at index <= i
  23.             if (sums.containsKey(nums[i] + target) && len1 < Integer.MAX_VALUE) {
  24.                 int len2 = sums.get(nums[i] + target) - i;
  25.                 ans = Math.min(ans, len1 + len2);
  26.             }
  27.         }
  28.        
  29.         return ans == Integer.MAX_VALUE ? -1 : ans;
  30.     }
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement