有N颗珠子,每颗珠子有不同种颜色,取出M种颜色包含珠子最多的

有N颗珠子,每颗珠子有不同种颜色,取出M种颜色包含珠子最多的

用暴力破解法很快，
两个指针分别表示最短包含m种颜色珠子的最短子串的首尾，这个很容易想到，但是要考虑清楚边界条件，为什么说这个子串是最短的，需要一个边界条件（最短序列中，包含首尾的珠子的颜色的个数一定是1）。例如：赤橙黄绿青蓝紫，就是最短子串（首尾珠子的颜色赤、紫，该序列包含赤、紫颜色的珠子各1个），而 赤橙黄绿赤青蓝紫 一定不是最短子串（因为首位的珠子是赤色，而包含赤色的珠子共两颗，因此，最短子串是 橙黄绿赤青蓝紫）。
bool judgeColors(vector colors) { for (int i = 0; i < colors.size(); i++) { if (!colors[i]) { return false;
}
} return true;
}int findMcolors(vector colors, int n, int m) { int ans = n + 1; int l = 0, r = 0; vector index(m, 0); while (r < n) {
index[colors[r++] - 1]++; while (judgeColors(index)) { if (index[colors[l] - 1] == 1) {
ans = (r - l) > ans ? ans : (r - l);
}
index[colors[l++] - 1]--;
}
} if (ans > n) { return -1;
} return ans;
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息