1. 剑指offer57 II 和为s的连续正数序列

问题描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

思路

滑动窗口 ：窗口左右两端都只能向右移动，当和小于sum时，j++，和大于sum时，i++，和等于sum就记录下窗口中i —j 中的序列，然后窗口继续后移，查找下一个满足条件的序列。

代码

func findContinuousSequence(target int) [][]int {
    var res [][]int
    l, r, sum := 1, 1, 0

    for l <= target / 2 {
        if sum == target {
            // 收集结果
            var ans []int = make([]int, r - l)
            for i := l; i < r; i++ {
                ans[i - l] = i
            }
            res= append(res, ans)
            
            sum -= l
            l++
        } else if sum < target {
            sum += r
            r++
        } else {
            sum -= l
            l++
        }
    }
    return res
}

2. 剩余最小磁盘

问题描述

某一个大文件被拆成了N个小文件，每个小文件编号从0至N-1，相应大小分别记为S(i)。给定磁盘空间为C，试实现一个函数从N个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小。

思路

滑动窗口 ：每次记录窗口内的总和，和小于C，记录剩余空间，再窗口右端右移，和大于C，就窗口左端右移，小于C情况下比较剩余空间取最小值。

代码

func findMin(s []int, c int) {
	i, j := 0, 0
	minValue := math.MaxInt32
	var sum int
	left, right := 0, 0
	
	for j <= len(s) {
		if sum <= c {
			j++
			sum += s[j]
			minValue = min(value, c - sum)
			if minValue == c - sum {
				left = i
				right = j
			}
		} else {
			i++
			sum -= s[i]
		}
	}

	nums := make([]int, right - left)
	for k := left; k < right; k++ {
		nums[k - left] = s[k]	
	}
	return nums
}

3. LeetCode 567字符串的排列

问题描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，s1 的排列之一是 s2 的 子串 。

思路

可以使用 长为m的滑动窗口遍历字符串 ，窗口内每个字符都要出现一次，如果符合条件，就返回窗口true。

代码

代码1.超时

func checkInclusion(s1 string, s2 string) bool {
    l, r := 0, len(s1)
    s2Byte :=[]byte(s2)

    for r <= len(s2) {
        // fmt.Printf("%d,%d,%t\n",len(s1),len(s2Byte[l:r]),matches(s1, string(s2Byte[l:r])))
        if matches(s1, string(s2Byte[l:r])) == true {
            return true
        }
        l++
        r++
    }
    return false
}

func matches(s1 string, subS2 string) bool {
    s1Map := map[byte]int{}

    for i := 0; i < len(s1); i++ {
        s1Map[s1[i]]++
    }

    for i := 0; i < len(subS2); i++ {
        s1Map[subS2[i]]--
    }

    for _, value := range s1Map {
        if value != 0 {
            return false
        }
    }
    return true
}

代码2. 通过

这种写法的好处在于，可以直接用==判断两个数组中的元素是否相等。

func checkInclusion(s1 string, s2 string) bool {
   lenS1, lenS2 := len(s1), len(s2)

   if lenS1 > lenS2 {
       return false
   }

   var count1, count2 [26]int

   for i, value := range s1 {
       count1[value - 'a']++
       count2[s2[i] - 'a']++
   }
   if count1 == count2 {
       return true
   }

   for i := lenS1; i < lenS2; i++ {
       count2[s2[i] - 'a']++
       count2[s2[i - lenS1] - 'a']--
       if count1 == count2 {
            return true
       }
   }
   return false
}