**关键字:**连续数组/字串
1.和为s的连续正整数序列(剑指offer57-II)
输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
示例 1:
输入:target = 9
输出:[[2,3,4],[4,5]]
滑动窗口:窗口左右两端都只能向右移动,当和小于sum时,j++,和大于sum时,i++,和等于sum就记录下窗口中i —j 中的序列,然后窗口继续后移,查找下一个满足条件的序列。
class Solution {
public int[][] findContinuousSequence(int target) {
int i = 1;
int j = 1;
int sum = 0;
List<int[]> list = new ArrayList<>();
//序列是由小到大排列,所以如果i>target/2,那么i+i+1肯定大于target
while(i <= target/2){
if(sum < target){
sum += j;
j++;
}else if(sum > target){
sum -= i;
i++;
}else{
int[] res = new int[j - i];
for(int z = i; z < j;z++){
res[z - i] = z;
}
list.add(res);
// 左边界向右移动
sum -= i;
i++;
}
}
return list.toArray(new int[list.size()][]);
}
}
2.某一个大文件被拆成了N个小文件
每个小文件编号从0至N-1,相应大小分别记为S(i)。给定磁盘空间为C,试实现一个函数从N个文件中连续选出若干个文件拷贝到磁盘中,使得磁盘剩余空间最小。
滑动窗口:每次记录窗口内的总和,和小于C,记录剩余空间,再窗口右端右移,和大于C,就窗口左端右移,小于C情况下比较剩余空间取最小值。
public class Solution {
public int[] findMin(int[] s,int c){
int i = 0;
int j = 0;
int minValue = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
int right = 0;
while(j <= s.length){
if(sum <= c){
j++;
sum += s[j];
minValue = Math.min(minValue,c - sum);
if(minValue == c - sum){
left = i;
right = j;
}
}else{
i++;
sum -= s[i];
}
}
int nums = new int[right - left];
for(int k = left;k < right;k++){
nums[k - left] = s[k];
}
return nums;
}
}
567. 字符串的排列
题目描述
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False
注意:
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
思路:2个字符串的排列 相等 -> 2个字符串 各个字符 的个数都一一相等。
每次扫描s2与s1相同长度的字串,固定窗口滑动
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n =s1.length(),m=s2.length();
if(n>m) return false;
int[] arr1 = new int[26];
int[] arr2 = new int[26];
//s1字串长度计算
for(int i=0;i<n;i++){
arr1[s1.charAt(i)-'a']++;
arr2[s2.charAt(i)-'a']++;
}
//若不同,则滑动窗口
for(int i=n;i<m;i++){
if(isEqual(arr1,arr2)){
return true;
}
arr2[s2.charAt(i)-'a']++;
arr2[s2.charAt(i-n)-'a']--;
}
return isEqual(arr1,arr2);
}
//判断当前字串是否相同
public boolean isEqual(int[] arr1,int[] arr2){
for(int i=0;i<arr1.length;i++){
if(arr1[i]!=arr2[i]){
return false;
}
}
return true;
}
}
4.给定m个不重复的字符 [a, b, c, d],
以及一个长度为n的字符串tbcacbdata,问能否在这个字符串中找到一个长度为m的连续子串,使得这个子串刚好由上面m个字符组成,顺序无所谓,返回任意满足条件的一个子串的起始位置,未找到返回-1。比如上面这个例子,acbd,3。
本题的子串需要满足长度为m,字符不重复,可以使用长为m的滑动窗口遍历字符串,窗口内每个字符都要出现一次,如果符合条件,就返回窗口起始位置。
class Solution {
public int checkInclusion(char[] ch,String s) {
int n = s.length();
int m =ch.length;
if(m>n) return -1;
for(int i=0;i<n-m;i++){
if(checkEqual(ch,s.substring(i,i+m))){
return i;
}
}
return -1;
}
public boolean checkEqual(char[] ch,String s){
for(int i=0;i<ch.length;i++){
if(s.indexOf(ch[i])==-1){
return false;
}
}
return true;
}