合并区间、哈希求最长连续序列、前缀和优化

850 员工空闲时间

我们得到一个员工的schedule列表,代表每个员工工作时间。

每个员工有一个不重合时段的列表 Intervals,这些时段按序排列。

返回一个所有员工共有的空闲时段的列表，并按序排列。

我们的Intervals是一个一维数组，其中每两个数表示一个区间，即[1,2,8,10]表示这个员工的工作时间是[1,2]和[8,10]。

并且,我们的答案不会包括像[5,5]这样的,因为它们的长度是0。

schedule 和 schedule[i] 为长度范围在 [1, 100]的列表。
0 <= schedule[i].start < schedule[i].end <= 10^8。

样例 1:

输入：schedule = [[1,2,5,6],[1,3],[4,10]]
输出：[(3,4)]
解释：共有三个员工,并且所有员工共有的空闲时段是[-inf, 1], [3, 4], [10, inf]。去除掉包含inf的答案。

样例 2:

输入：schedule = [[1,3,6,7],[2,4],[2,5,9,12]]
输出：[(5,6),(7,9)]
解释：共有三个员工,并且所有员工共有的空闲时段是[-inf, 1], [5, 6], [7, 9],[12,inf]。去除掉包含inf的答案。

合并区间

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param schedule: a list schedule of employees
     * @return: Return a list of finite intervals 
     */
    public List<Interval> employeeFreeTime(int[][] schedule) {
        // 合并区间
        List<List<Integer>> list = new ArrayList<>();
        for(int i=0;i<schedule.length;i++) {
            for(int j=0;j<schedule[i].length;j+=2) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(schedule[i][j]);
                tmp.add(schedule[i][j+1]);
                list.add(tmp);
            }
        }

        Collections.sort(list,(a,b)->{
            if(a.get(0)==b.get(0)) return a.get(1)-b.get(1);
            return a.get(0)-b.get(0);
        });

        List<List<Integer>> result = new ArrayList<>();
        result.add(list.get(0));
        for(int i=1;i<list.size();i++) {
            if(list.get(i).get(0)>result.get(result.size()-1).get(1)) {
                result.add(list.get(i));
            } else {
                if(list.get(i).get(1)>result.get(result.size()-1).get(1)) {
                    result.get(result.size()-1).set(1,list.get(i).get(1));
                }
            }
        }
        //System.out.println(result);
        List<Interval> ret = new ArrayList<>();
        for(int i=1;i<result.size();i++) {
            Interval interval = new Interval(result.get(i-1).get(1),result.get(i).get(0));
            ret.add(interval);
        }
        return ret;
    }
}

128. 最长连续序列

排序然后遍历

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length<=1) return nums.length;
        Arrays.sort(nums);

        int last = nums[0];
        int result = 1;
        int curLen = 1;
        for(int i=0;i<nums.length;i++) {
            if(nums[i]==last) continue;
            if(nums[i]==last+1) {
                last = nums[i];
                curLen++;
            } else {
                result = Math.max(result,curLen);
                curLen = 1;
                last = nums[i];
            }
        }
        return Math.max(result,curLen);
    }
}

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

O(n)解法没想到。

哈希O(n)解法

这个思路挺巧妙的，放入set，然后关键的来了：对于集合元素只考虑连续序列里面开始的那个（根据当前元素-1是否存在，不存在则是队首）。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++) {
            set.add(nums[i]);
        }

        int result = 0;
        int curLen;

        for(int k:set) {
            if(!set.contains(k-1)) {
                curLen = 1;
                while(set.contains(k+1)) {
                    curLen++;
                    k++;
                }
                result = Math.max(result,curLen);
            }
        }
        return result;
    }
}

并查集

这个题用并查集的思想倒也正合适，但是涉及到合并和查找父节点，经过路径压缩之后效率最好应该也是O(nlogn)级别。

560. 和为 K 的子数组

和数组然后遍历

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] sums = new int[n+1];
        sums[0] = 0;
        for(int i=1;i<=n;i++) {
            sums[i] = sums[i-1]+nums[i-1];
        }

        int count = 0;
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<=n;j++) {
                if(sums[j]-sums[i]==k) count++;
            }
        }
        return count;
    }
}

前缀和优化

真尼玛是妙蛙种子妙到家了。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int preSum = 0;
        int result = 0;
        Map<Integer,Integer> map = new HashMap<>();

        map.put(0,1);
        for(int i=0;i<nums.length;i++) {
            preSum+=nums[i];
            if(map.containsKey(preSum-k)) {
                result+=map.get(preSum-k);
            }
            map.put(preSum,map.getOrDefault(preSum,0)+1);
        }
        return result;
    }
}

这才叫前缀和啊。