Sliding Window

Conditions

contiguous subarrays (or sublists) of a given size

Questions

209

 class Solution {
     public int minSubArrayLen(int target, int[] nums) {
         int n = nums.length;
         int left = 0, right = 0, sum = 0, minLen = Integer.MAX_VALUE;

         // Loop through the array using two pointers: left and right
         while (right < n) {
             // Add the current number to the sum
             sum += nums[right];

             // If the sum is greater than or equal to the target,
             // move the left pointer until the sum becomes less than the target
             while (sum >= target) {
                 // Update the minimum length
                 minLen = Math.min(minLen, right - left + 1);

                 // Remove the leftmost number from the sum
                 sum -= nums[left];

                 // Move the left pointer to the next index
                 left++;
             }

             // Move the right pointer to the next index
             right++;
         }

         // Return 0 if the minimum length is not updated, otherwise return the minimum length
         return minLen == Integer.MAX_VALUE ? 0 : minLen;
     }
 }

862

class Solution {
    public int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] prefixSum = new long[n + 1]; // Prefix sum array to keep track of sums up to each index
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    int minLength = n + 1; // Initialize the minimum length to be larger than the input array size
    Deque<Integer> deque = new LinkedList<>(); // Deque to keep track of indices

    for (int i = 0; i <= n; i++) { // Iterate through the prefix sum array
        while (!deque.isEmpty() && prefixSum[i] - prefixSum[deque.peekFirst()] >= k) {
            // If the current prefix sum minus the prefix sum at the front of the deque is greater than or equal to k,
            // it means we found a subarray that satisfies the condition, so we update the minimum length accordingly
            minLength = Math.min(minLength, i - deque.pollFirst());
        }

        while (!deque.isEmpty() && prefixSum[i] <= prefixSum[deque.peekLast()]) {
            // This loop removes indices from the back of the deque as long as the prefix sum at the current index
            // is less than or equal to the prefix sum at the back of the deque. This helps maintain a monotonic
            // increasing deque.
            deque.pollLast();
        }

        deque.addLast(i); // Add the current index to the deque
    }

    return minLength == n + 1 ? -1 : minLength; // If no subarray satisfies the condition, return -1
}

}

340

  class Solution {
      public int lengthOfLongestSubstringKDistinct(String s, int k) {
          int n = s.length();
          if (n * k == 0) return 0;
          int left = 0, right = 0;
          Map<Character, Integer> hashmap = new HashMap<>();
          int max_len = 1;

          while (right < n) {
              // add new character and move right pointer
              hashmap.put(s.charAt(right), right++);

              // if number of distinct characters exceeds k, remove the leftmost character
              if (hashmap.size() > k) {
                  int min_idx = Collections.min(hashmap.values());
                  hashmap.remove(s.charAt(min_idx));
                  left = min_idx + 1;
              }

              // update maximum length
              max_len = Math.max(max_len, right - left);
          }

          return max_len;
      }
  }

3

  class Solution {
      public int lengthOfLongestSubstring(String s) {
          // Initialize variables
          int n = s.length();
          Set<Character> set = new HashSet<>();
          int left = 0, right = 0, maxLen = 0;

          // Use sliding window technique
          while (left < n && right < n) {
              // If the current character is not in the set, add it to the set and move the right pointer
              if (!set.contains(s.charAt(right))) {
                  set.add(s.charAt(right++));
                  maxLen = Math.max(maxLen, right - left); // Update the maximum length
              }
              // If the current character is in the set, remove the leftmost character from the set and move the left pointer
              else {
                  set.remove(s.charAt(left++));
              }
          }

          return maxLen;
      }
  }

424

  class Solution {
      public int characterReplacement(String s, int k) {
          int[] count = new int[26]; // count the frequency of each character in the current window
          int maxCount = 0; // the max frequency of a single character in the current window
          int start = 0; // the start index of the current window
          int maxLength = 0; // the max length of the substring with repeating characters
          for (int end = 0; end < s.length(); end++) {
              char ch = s.charAt(end);
              count[ch - 'A']++;
              maxCount = Math.max(maxCount, count[ch - 'A']);
              // if the number of characters that need to be changed (k) is less than the length of the window minus the max count, we can still make all the characters in the window the same by replacing some of them
              while (end - start + 1 - maxCount > k) {
                  char leftChar = s.charAt(start);
                  count[leftChar - 'A']--;
                  start++;
              }
              maxLength = Math.max(maxLength, end - start + 1); // update the max length
          }
          return maxLength;
      }
  }

1004

  class Solution {
      public int longestOnes(int[] nums, int k) {
      int left = 0; // left pointer of the sliding window
      int right = 0; // right pointer of the sliding window
      int maxOnes = 0; // maximum number of consecutive ones seen so far
      int zeros = 0; // number of zeros seen in the current window so far

      while (right < nums.length) {
          if (nums[right] == 0) { // if the current number is zero
              zeros++; // increment the count of zeros
          }

          while (zeros > k) { // if there are more than k zeros in the current window
              if (nums[left] == 0) { // if the leftmost number is zero
                  zeros--; // decrement the count of zeros
              }
              left++; // move the left pointer to the right to shrink the window
          }

          // update the maximum number of consecutive ones seen so far
          maxOnes = Math.max(maxOnes, right - left + 1);

          right++; // move the right pointer to the right to expand the window
      }

      return maxOnes; // return the maximum number of consecutive ones seen
  }

  }

567
438
76
1248
1234
930
904
2024
713

Conclusion

Two Pointer

Conditions

sorted arrays (or LinkedLists) and need to find a set of elements that fulfill certain constraints

Questions

167

 /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 class Solution {
     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
     // Base case: if either list is null, return the other list
     if (list1 == null) {
         return list2;
     } else if (list2 == null) {
         return list1;
     }

     // Recursive case: compare the values at the current nodes of both lists
     if (list1.val < list2.val) {
         // If the value in l1 is smaller, merge the rest of l1 with the remaining nodes in l2
         list1.next = mergeTwoLists(list1.next, list2);
         return list1;
     } else {
         // If the value in l2 is smaller, merge the rest of l2 with the remaining nodes in l1
         list2.next = mergeTwoLists(list1, list2.next);
         return list2;
     } 
     }
 }

Conclusion

Fast & Slow Pointer

Conditions

Hare & Tortoise algorithm (or Floyd’s cycle-finding algorithm)

Questions

141

 /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 class Solution {
     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
     // Base case: if either list is null, return the other list
     if (list1 == null) {
         return list2;
     } else if (list2 == null) {
         return list1;
     }

     // Recursive case: compare the values at the current nodes of both lists
     if (list1.val < list2.val) {
         // If the value in l1 is smaller, merge the rest of l1 with the remaining nodes in l2
         list1.next = mergeTwoLists(list1.next, list2);
         return list1;
     } else {
         // If the value in l2 is smaller, merge the rest of l2 with the remaining nodes in l1
         list2.next = mergeTwoLists(list1, list2.next);
         return list2;
     } 
     }
 }

Conclusion

「少种的少收，多种的多收,捐款会鼓励作者多创作以及教会福音传播!!」