LeetCode 解題筆記：835. Image Overlap

作者：王一哲
日期：2026年9月13日


LeetCode 題目連結：835. Image Overlap

解題想法

中等難度題，題目給兩個大小皆為 $n \times n$ 的二維陣列 $img1, img2$，陣列之中只有 $0$ 或　$1$，可以將 $img1$ 往上、下、左、右平移，刪除出界的部分，將兩個陣列重疊，計算兩個陣列中有幾個 $1$ 重疊，回傳最大的數量。

可以先用兩層 for 迴圈掃過 $img1, img2$，將陣列中 $1$ 的位置分別存到陣列 $pos1, pos2$ 之中。再開一個字典，以坐標平移量 $dr, dc$ 為 key，計算各種位移量下重疊的 $1$ 有幾個，同時更新答案 $ans$。

Python 程式碼

Runtime: 259 ms, beats 48.41%. Memory: 19.95 MB, beats 14.29%.

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        # 記錄影像 1、2 之中 1 的位置
        n = len(img1)
        pos1, pos2 = [], []
        for r in range(n):
            for c in range(n):
                if img1[r][c] == 1:
                    pos1.append((r, c))
                if img2[r][c] == 1:
                    pos2.append((r, c))
        # 計算所有平移量 (dr, dc) 影像中 1 重疊的數量
        ans = 0  # 答案，預設為 0
        cnt = defaultdict(int)  # (dr, dc): ones
        for r1, c1 in pos1:
            for r2, c2 in pos2:
                dr, dc = r1 - r2, c1 - c2
                cnt[dr, dc] += 1
                if cnt[dr, dc] > ans:
                    ans = cnt[dr, dc]
        return ans

C++ 程式碼

Runtime: 136 ms, beats 29.15%. Memory: 16.02 MB, beats 21.97%.

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        // 記錄影像 1、2 之中 1 的位置
        int n = (int)img1.size();
        vector<pair<int, int>> pos1, pos2;
        for(int r = 0; r < n; r++) {
            for(int c = 0; c < n; c++) {
                if (img1[r][c] == 1) {
                    pos1.push_back(make_pair(r, c));
                }
                if (img2[r][c] == 1) {
                    pos2.push_back(make_pair(r, c));
                }
            }
        }
        // 計算所有平移量 (dr, dc) 影像中 1 重疊的數量
        int ans = 0;
        map<pair<int, int>, int> cnt;
        for(auto it1 : pos1) {
            for(auto it2 : pos2) {
                pair<int, int> d = make_pair(it1.first - it2.first, it1.second - it2.second);
                cnt[d]++;
                if (cnt[d] > ans) {
                    ans = cnt[d];
                }
            }
        }
        return ans;
    }
};