给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。
如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/continuous-subarray-sum
示例 1：
输入：nums = [23,2,4,6,7], k = 6 输出：true 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
#include "sstream" #include "cstdlib" #include "iostream" #include "vector" #include "unordered_map" using namespace std; class Solution { public: static bool checkSubarraySum(vector<int> &nums, int k) { // 连续的子数组和 int m = nums.size(); if (m<2) { return false; } unordered_map<int, int> mp; mp[0] = 1; int remainder = 0; for (int i=0; i<m; i++) { remainder = (remainder + nums[i]) % k; if (mp.count(remainder)) { int prevIndex = mp[remainder]; if (i - prevIndex >= 2) { return true; } } else { mp[remainder] = i; } } return false; } }; vector<string> split(string str, const char c) { // 不支持“, ”、“; ”等带空格的字符串，支持类似‘,‘、‘;‘等这样的字符 vector<string> sstr; int pos = 0; while (pos < str.length()) { int end; // 记住这种for的方式 for (end = pos; (end < str.length()) && (str[end] != c); end++); sstr.push_back(str.substr(pos, end-pos)); pos = end+1; } return sstr; } vector<string> splitSpace(string str) { // 去除空格 istringstream strs(str); vector<string> words; string word; while (strs >> word) { words.push_back(word); } return words; } vector<int> stringToInt(vector<string> &ss2) { vector<int> dest; for (int i=0; i<ss2.size(); i++) { dest.push_back(atoi(ss2[i].c_str())); } return dest; } int main() { string inputs; while (getline(cin, inputs)) { vector<string> ss1 = splitSpace(inputs); // nums string numString = ss1[2]; // 从第一个[的位置开始的1个字符替换成"" string numString1 = numString.replace(numString.find("["), 1, ""); // 删除], string numString2 = numString1.replace(numString1.find("]"), 2, ""); // k string kString = ss1[5]; // #include <cstdlib> int k = atoi(kString.c_str()); // 不支持“, ”、“; ”等带空格的字符串，支持类似‘,‘、‘;‘等这样的字符 vector<string> ss2 = split(numString2, ‘,‘); vector<int> dest = stringToInt(ss2); // 把bool型输出成true或者false,而不是1,0 cout << boolalpha << Solution::checkSubarraySum(dest, k) << endl; } return 0; }
c++实现split()函数的功能:
vector<string> split(string str, const char c) { // 不支持“, ”、“; ”等带空格的字符串，支持类似‘,‘、‘;‘等这样的字符 vector<string> sstr; int pos = 0; while (pos < str.length()) { int end; // 记住这种for的方式 for (end = pos; (end < str.length()) && (str[end] != c); end++); sstr.push_back(str.substr(pos, end-pos)); pos = end+1; } return sstr; }
去重空格:
vector<string> splitSpace(string str) { // 去除空格 istringstream strs(str); vector<string> words; string word; while (strs >> word) { words.push_back(word); } return words; }
string向量转换为int向量：
vector<int> stringToInt(vector<string> &ss2) { vector<int> dest; for (int i=0; i<ss2.size(); i++) { dest.push_back(atoi(ss2[i].c_str())); } return dest; }
测试用例连续输入或一起输入：
int main() { string inputs; while (getline(cin, inputs)) { vector<string> ss1 = splitSpace(inputs); // nums string numString = ss1[2]; // 从第一个[的位置开始的1个字符替换成"" string numString1 = numString.replace(numString.find("["), 1, ""); // 删除], string numString2 = numString1.replace(numString1.find("]"), 2, ""); // k string kString = ss1[5]; // #include <cstdlib> int k = atoi(kString.c_str()); // 不支持“, ”、“; ”等带空格的字符串，支持类似‘,‘、‘;‘等这样的字符 vector<string> ss2 = split(numString2, ‘,‘); vector<int> dest = stringToInt(ss2); // 把bool型输出成true或者false,而不是1,0 cout << boolalpha << Solution::checkSubarraySum(dest, k) << endl; } return 0; }
原文：https://www.cnblogs.com/zhangwenzhi/p/14843015.html
