Java, O(n), only 3 int extra Space, easy to understand


  • 0
    J

    public List<Integer> findAnagrams(String s, String p) {
    if (s == null || p == null || s.length() < p.length())
    return null;

    	List<Integer> result = new ArrayList<>();
    	
    	// get sum of p
    	int pLen = p.length(), pSum = 0, sSubSum = 0;
    	for(int i = 0; i < pLen; i++){
    		pSum += p.charAt(i);
    		sSubSum += s.charAt(i);
    	}
        
    	// check sum
    	sSubSum -= s.charAt(pLen-1);
    	for(int i = pLen-1; i < s.length(); i++){	
    		sSubSum += s.charAt(i);
    		
    		if(sSubSum == pSum){
    			result.add(i - (pLen-1));
    		}
    		
    		sSubSum -= s.charAt(i - (pLen-1));
    	}
    	
    	return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.