4. 子串/子数组、子序列问题

718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

class Solution {
    public int findLength(int[] A, int[] B) {
        int lenA = A.length, lenB = B.length;
        int res = 0;
        int[][] dp = new int[lenA+1][lenB+1];
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(dp[i][j], res);   
            }
        }
        return res;
    }
}

560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

package code
# subarray.go
// a,b都为有序数组, 判断a是否为b的子数组
func IsSubArray(a []int, b []int) bool {
    m, n := len(a), len(b)
    if m == 0 || m > n {
        return false
    }
    for j := 0; j < n; j++ {
        i := 0
        s := j
        for i < m && s < n {
            if a[i] == b[s] {
                i++
                s++
            } else {
                break
            }
        }
        if i == m {
            return true
        }
    }
    return false
}

package code
# subarray_test.go

import (
    "reflect"
    "testing"
)

func TestIsSubArray(t *testing.T) {
    type testCase struct {
        arrA []int
        arrB []int
        want bool //期望的结果
    }
    testGroup := map[string]testCase{
        "case1": testCase{[]int{3, 4}, []int{1, 2, 3, 3, 4, 5}, true},
        "case2": testCase{[]int{3, 5}, []int{1, 2, 3, 3, 4, 5}, false},
        "case3": testCase{[]int{3, 3}, []int{1, 2, 3, 3, 3, 3}, true},
        "case4": testCase{[]int{1, 3, 4}, []int{1, 3, 5}, false},
    }

    for key, v := range testGroup { //遍历
        t.Run(key, func(t *testing.T) {
            got := IsSubArray(v.arrA, v.arrB)
            want := v.want
            if !reflect.DeepEqual(want, got) { //比较
                t.Errorf("excepted:%v, got:%v", want, got)
            }
        })
    }
}