Continuous subarray sum

Array Hash Table Math Prefix Sum

31.2% acceptance

Feb 19, 2026

6920

717

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise. A good subarray is a subarray where: its length is at least two, and the sum of the elements of the subarray is a multiple of k. Note that: A subarray is a contiguous part of the array. An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;
impl Solution {
  pub fn check_subarray_sum(nums: Vec<i32>, k: i32) -> bool {
    let mut map: HashMap<i32, i32> = HashMap::new();
    map.insert(0, -1);
    let mut sum = 0i32;
    for (i, &n) in nums.iter().enumerate() {
      sum = (sum + n) % k;
      if let Some(&prev) = map.get(&sum) {
        if i as i32 - prev >= 2 { return true; }
      } else {
        map.insert(sum, i as i32);
      }
    }
    false
  }
}