Can I see which companies don't have deals?

You are able to view companies that don't have a Deal association by adding the 'Has Deals' field to your list view in the Companies tab. 

Then, click the column header and filter 'No'