2260. Minimum Consecutive Cards to Pick Up

Question

You are given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.

Solution

动态规划的思想。

found[]储存每个数字的上一个index

遍历，当数字相同时从found里获得上一个index，计算当前index与last index的距离。

并保存最小值。

Code

class Solution {
    public int minimumCardPickup(int[] cards) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < cards.length; i++){
            max = Math.max(max, cards[i]);
        }
        int[] found = new int[max+1];

        for(int i = 0; i < found.length; i++){
            found[i] = -1;
        }

        for(int i = 0; i < cards.length; i++){
            int cur = cards[i];
            if(found[cur] != -1){
                min = Math.min(min, i - found[cur] + 1);
            }
            found[cur] = i;
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}